Question 1210668: You have a total supply of 1000 pieces of candy, and an empty vat. You also have a machine that can add exactly 123 pieces of candy per scoop to the vat, and another machine that can remove exactly 23 pieces of candy with a different scoop from the vat. When these two machines are done, there is only one piece of candy left in the vat. What is the smallest possible number of times the first machine added candy to the vat?
Found 2 solutions by greenestamps, math_tutor2020:
Answer by greenestamps(13374)   (Show Source):
Answer by math_tutor2020(3842)  (Show Source):
You can put this solution on YOUR website!
x = number of scoops the first machine adds
y = number of scoops the second machine removes
x,y are positive whole numbers.
123x = number of pieces of candy the first machine adds
23y = number of pieces of candy the second machine removes
123x - 23y = amount of candy left over when both machines are operational
Since we want one piece remaining, we establish this equation
123x - 23y = 1
Finding an (x,y) solution, where x & y are integers, involves solving a linear Diophantine equation.
One way to solve such an equation is to find the GCD of 123 and 23.
I'll use the Extended Euclidean Algorithm.
Note that 123/23 = 5.3478 roughly, so the divisor 23 goes in 5 whole times with 123 - 23*5 = 8 as the remainder.
We can rewrite that as
123 = 23*5 + 8
The format of this is: divisor*quotient + remainder.
The old divisor 23 is then treated as the new dividend while the remainder 8 is the new divisor. Everything gets shifted.
We have 23/8 = 2.875 exactly, so the quotient is 2 and remainder is 23-8*2 = 7.
In other words,
23 = 8*2 + 7
Then,
8 = 7*1 + 1
and
7 = 1*7 + 0
Once arriving at a remainder of 0, we know to stop the first section of this algorithm.
Here's what it looks like as one big block
123 = 23*5 + 8
23 = 8*2 + 7
8 = 7*1 + 1
7 = 1*7 + 0
The last nonzero remainder is the GCD of 123 and 23, which is highlighted in red.
Therefore the GCD is 1.
--------------------------------------------------------------------------
Let's ignore the last row of that block since it technically isn't used for this next part.
Here is the updated shorter block.
123 = 23*5 + 8
23 = 8*2 + 7
8 = 7*1 + 1
Isolate each remainder.
8 = 123 - 23*5
7 = 23 - 8*2
1 = 8 - 7*1
The goal is to arrive at something of the form 123x - 23y = 1, where x and y are integers.
To do this we start at the bottom, and work our way upward, by applying substitutions.
Note the repeated "7"s in the last two equations.
This is not a coincidence because things got shifted (as mentioned earlier).
Let's replace the bottom 7 with 23-8*2
1 = 8 - 7*1
1 = 8 - (23 - 8*2)*1
1 = 8 - 23*1 + 8*2
1 = 8*3 - 23*1
We have the coefficient 23 in there, but the 8 should be 123 instead.
To get rid of that 8, apply the equation 8 = 123 - 23*5
So,
1 = 8*3 - 23*1
1 = (123 - 23*5)*3 - 23*1
1 = 123*3 - 23*5*3 - 23*1
1 = 123*3 - 23*15 - 23*1
1 = 123*3 - 23*(15 + 1)
1 = 123*3 - 23*16
123*3 - 23*16 = 1
We see that (x,y) = (3,16) is an integer solution to the equation 123x - 23y = 1
It is one of infinitely many integer solutions.
To arrive at other integer solutions we apply the slope.
The slope of Ax + By = C is -A/B.
The slope of 123x - 23y = 1 is 123/23.
It tells us to move 123 units up and 23 units right.
Or rephrased a bit:
* move 23 units right (i.e. x goes to x+23)
* move 123 units up (i.e. y goes to y+123)
Telling us that (x,y) moves to (x+23, y+123)
This process in reverse has (x,y) move to (x-23, y-123)
Plugging x = 3 into x-23 yields a negative x coordinate; which shows we have the smallest positive integer solution for x.
To recap:
We used the Extended Euclidean Algorithm to find the GCD, then rewrote those sets of equations to find an integer solution.
That solution being (x,y) = (3,16)
The slope 123/23 can be used to find other integer solutions; but it turns out we already landed on the smallest positive integer for x.
Answer: 3 times
| |
|
