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?

Mellie Jun 28, 2015

#1**+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

CPhill Jun 28, 2015

#1**+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**+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

Melody Jul 1, 2015

#4**+5 **

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

CPhill Jul 1, 2015

#5**+5 **

Thanks Chris, we both need more practice at these.

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

Melody Jul 1, 2015

#6**+5 **

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

CPhill Jul 1, 2015