+0  
 
0
4301
8
avatar+1833 

You have a machine that can add exactly 46,899 pieces of candy per scoop to a giant vat and another machine that can remove exactly 13,576 pieces of candy with a different scoop from the giant vat. You have a total supply of 600,000 pieces of candy. Your giant vat starts out empty. The first machine adds scoops of candy, and then the second machine removes scoops of candy. At the end of this process, there is only one piece of candy left in the vat. How many scoops of candy did the first machine add to the vat?

 Jun 28, 2015

Best Answer 

 #1
avatar+128408 
+15

There are probably easier ways to do this.....but....here's my reasoning.......

 

The "filling" scoop has to operate an odd number of times, because 46,899 *  an odd will produce an odd. And the "removing"  scoop always removes an even number of candies. So, the difference between an odd and an even is always an odd......

 

Let's say the flling scoop operates once and the removing scoop operates 3 times......then the number of candies left in the vat is just  46899 mod (3*13576) =  6171

 

Now...let's say that the filling scoop operates 3 times = 140697 candies added to the vat ....and that the removing scoop operates 10 times = 135760 candies removed from the vat

 

Then 140697 mod 135760 = 4937 ....  and 6171 - 4937 = 1234

 

Lastly....let the filling scoop operate 5 times = 234495 candies added to the vat, and let the "removing" scoop operate 17 times = 230792 candies removed from the vat

 

Then 234495 mod 230792 = 3703   =  6171 x 2(1234)

 

Notice the patern.....for every 2n - 1 times the "filling" scoop operates and for every 3 + 7(n-1) times the "removing" scoop operates, the mod remainder after the first time (where n = 1) = (6171) ... and this is reduced by 1234 for each successive integer value of "n"

 

So.....  6171/1234 = 5

 

This means that, when the "filling" scoop operates n = 5 more times after the first operation, i.e., 2(6) - 1 = 11 total times, the number of candies put into the vat is 11*46899  = 515889.  And the removing scoop will have operated 3 + 7(6-1)  = 38 times  in which 38 * 13576 = 515888 candies have been removed from the vat.....so..... 515889 added - 515888 removed = 1 remaining candy in the vat.....

 

[I'm pretty sure that there is some sort of algorithm for solving this......but....I'm not familiar with what it might be....!!! ]

 

P.S. - I believe this can also be solved by using something known as a"Diophantine" Equation.....I'm not familiar with this technique, but I'm reading about it here.....http://www.wikihow.com/Solve-a-Linear-Diophantine-Equation

 

 

 

 Jun 28, 2015
 #1
avatar+128408 
+15
Best Answer

There are probably easier ways to do this.....but....here's my reasoning.......

 

The "filling" scoop has to operate an odd number of times, because 46,899 *  an odd will produce an odd. And the "removing"  scoop always removes an even number of candies. So, the difference between an odd and an even is always an odd......

 

Let's say the flling scoop operates once and the removing scoop operates 3 times......then the number of candies left in the vat is just  46899 mod (3*13576) =  6171

 

Now...let's say that the filling scoop operates 3 times = 140697 candies added to the vat ....and that the removing scoop operates 10 times = 135760 candies removed from the vat

 

Then 140697 mod 135760 = 4937 ....  and 6171 - 4937 = 1234

 

Lastly....let the filling scoop operate 5 times = 234495 candies added to the vat, and let the "removing" scoop operate 17 times = 230792 candies removed from the vat

 

Then 234495 mod 230792 = 3703   =  6171 x 2(1234)

 

Notice the patern.....for every 2n - 1 times the "filling" scoop operates and for every 3 + 7(n-1) times the "removing" scoop operates, the mod remainder after the first time (where n = 1) = (6171) ... and this is reduced by 1234 for each successive integer value of "n"

 

So.....  6171/1234 = 5

 

This means that, when the "filling" scoop operates n = 5 more times after the first operation, i.e., 2(6) - 1 = 11 total times, the number of candies put into the vat is 11*46899  = 515889.  And the removing scoop will have operated 3 + 7(6-1)  = 38 times  in which 38 * 13576 = 515888 candies have been removed from the vat.....so..... 515889 added - 515888 removed = 1 remaining candy in the vat.....

 

[I'm pretty sure that there is some sort of algorithm for solving this......but....I'm not familiar with what it might be....!!! ]

 

P.S. - I believe this can also be solved by using something known as a"Diophantine" Equation.....I'm not familiar with this technique, but I'm reading about it here.....http://www.wikihow.com/Solve-a-Linear-Diophantine-Equation

 

 

 

CPhill Jun 28, 2015
 #2
avatar+118608 
+10

Thanks Chris,  I also would like to try this one.

 

We have this situation 

 

Let X be the number of scoops in and Y be the number of scoops out,  so X and Y are integers

 

$$46899X-13567Y=1$$      This is a diophantine equation because the solutions must be integers.

 

I'll rearrange this

 

$$\\46899X=13576Y+1\\\\
\frac{46899}{13576}*X=Y+\frac{1}{13576}\\\\
$I need the fraction part to be a proper fraction$
\frac{(3*13576+6171)}{13576}*X=Y+\frac{1}{13576}\\\\
3X+\frac{6171}{13576}*X=Y+\frac{1}{13576}\\\\
\frac{6171}{13576}*X=Y-3X+\frac{1}{13576}\\\\$$

 

Y-3X is an integer so I am going to replace it with Z  (I only care that it is an integer)

 

$$\\\frac{6171}{13576}*X=Z+\frac{1}{13576}\\\\
So\\
6171*X = 1 Mod\; 13576\\\\
X = \frac{1}{6171}\; Mod\; 13576\\\\
X = 6171^{-1}\;\; Mod\; 13576\\\\\\
$Now I am going to use the $ \underline{Euclidean\; Algorithm} \\\\
\begin{array}{rllll}
13576&=&\underline{6171}*2+\underline{1234}\qquad&(1a)\quad &1234=13576-6171*2\\\\
6171&=&\underline{1234}*5+\underline{1}\qquad&(2a)\quad &1=6171-1234*5\\\\
\end{array}
$I can stop the Euclidean algorithm now because I have the 1 that I wanted$\\\\
$Now I am going to use the \underline{Extended Euclidean Algorithm} and go 'backwards' :)$\\\\$$

 

$$\\\frac{6171}{13567}*X=Z+\frac{1}{13567}\\\\
So\\
6171*X = 1 Mod\; 13567\\\\
X = \frac{1}{6171}\; Mod\; 13567\\\\
X = 6171^{-1}\;\; Mod\; 13567\\\\\\
$Now I am going to use the Euclidean Algorithm$ \\\\
\begin{array}{rllll}
13576&=&\underline{6171}*2+\underline{1234}\qquad&(1a)\quad &1234=13576-6171*2\\\\
6171&=&\underline{1234}*5+\underline{1}\qquad&(2a)\quad &1=6171-1234*5\\\\
\end{array}
$I can stop the Euclidean algorithm now because I have the 1 that I wanted$\\\\
$Now I am going to use the extended Euclidean Algorithm and go 'backwards' :)$\\\\
\begin{array}{rllll}
1&=&6171-1234*5\qquad &(2b)\\\\
1&=&6171-(13576-6171*2)*5\qquad &(2a)\\\\
1&=&6171-5*13576+5*6171*2\qquad &(2a)\\\\
1&=&6171-5*13576+10*6171\qquad &(2a)\\\\
1&=&11*6171-5*13576\qquad &(2a)\\\\
&&$now 5*13576 mod 13576=0 so$\\\\
1&=&11*6171\\\\
\end{array}$$

 

So X=11

The number of scoops in is  11+13576N

But each scoop in is 46899 peices.

46899*(11+13576N)<600000

(11+13576N)<12.79

N has to be 0

SO  

The number of scoops in MUST be 11.        

 

Here are 3 lollipops, one for me, one for CPhill and one for Mellie.  

BECAUSE WE DESERVE THEM  

 

I just realized that some otf the LaTex was not displaying.

Hopefully there is no more problems.

Ref:  (only partly)   https://www.youtube.com/watch?v=fz1vxq5ts5I

 Jul 1, 2015
 #4
avatar+128408 
+5

Thanks for the lollipop, Melody......I'm going to add your answer to my "Watchlist" and look at it in more detail later......!!!!

 

 

  

 Jul 1, 2015
 #5
avatar+118608 
+5

Thanks Chris, we both need more practice at these.

Has Mellie posted other diophantine equation questions ?  I think she has ://

 Jul 1, 2015
 #6
avatar+128408 
+5

I think we should ask Mellie if she can actually spell "Diophantine"............LOL!!!!!

 

 

  

 Jul 1, 2015
 #7
avatar+118608 
+5

Yea well I can ....now    LOL

Although I still get muddled as to whether it is dio or dia  

BUT then I think - no it is definitely not a diaphram  :))

 Jul 1, 2015
 #8
avatar+118608 
+5

Hi Mellie,

Thanks for the points:)

Did you understand our answers ?

 Jul 1, 2015
 #9
avatar+1833 
0

Yeah. Thank you so much for helping me!! 

 Jul 1, 2015

1 Online Users