You have two jugs, capable of holding 31 and 21 gallons of water, respectively.
ID: 3569489 • Letter: Y
Question
You have two jugs, capable of holding 31 and 21 gallons of water, respectively. Unfortunately, neither jug is marked in any way that would allow you to measure how much water was in it if it was partially filled. You are also near a stream of clear, cold water, so at least you have an effectively infinite supply of water.
Is it possible for you to use your two jugs in such a way that on of them will contain exactly 1 gallon of water and the other jug is empty? If yes, how? If no, why not? Perform a linear Diophantine tabular analysis to justify your answer.
Explanation / Answer
Let x be the total number of times the 31-gallon jug has been filled from the stream or emptied into the stream. Count filling it as +1 and emptying as -1.
Total amount of water transferred between stream and 31-gallon jug = 31x
Let y be the total number of times the 21-gallon jug has been filled from the stream or emptied into the stream.
Total amount of water transferred between stream and 21-gallon jug = 21x
Total amount of water removed from the well = 31x + 21y
Find the values of x and y such that
31x + 21y=1
Both x and y should be integers.
The linear Diophantine equation is 31x+21y=1
A simple tabular method to solve the Diophantine equation ax + by = c, where c is the GCD of a and b, is shown below:
x
y
d
k
1
0
31
0
1
21
1 (31/21 with remainder 10
1
-1
10
2 (21/10 with remainder 1)
2
-3
1
10 (10/1 with remainder 0. Stop the process)
The solution is 31 * 2 + 21 * -3 =1
It means that to obtain the 1 gallon, fill the 31-gallon jug from the stream 2 times and empty the 21-gallon jug into the stream 3 times.
x
y
d
k
1
0
31
0
1
21
1 (31/21 with remainder 10
1
-1
10
2 (21/10 with remainder 1)
2
-3
1
10 (10/1 with remainder 0. Stop the process)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.