1

You want to prepare a tub for your favorite game, dunking for apples. You have two buckets. One of the buckets will hold $4$ liters of water and the other will hold $9$ liters. There are no markings on either bucket to indicate smaller quantities. How can you measure out $6$ liters of water using only these two buckets and the tub?

Yiyuan Lee
  • 14,435
prerna
  • 23
  • 1
    fill the 9 liter bucket with the 4 liter. You are left with 3 liter in the 4 liter bucket throw it in the tub. repeat. – Kaladin Mar 08 '14 at 02:18
  • 1
    based on the idea of @Kaladin: fill the 9 liter buckte and remove 2 time 4 liter with the 4 liter bucket then 1 liter remains. put this in the tube. so you can fill the tube win an arbitrary integer number of liters – miracle173 Mar 08 '14 at 02:29

2 Answers2

3

This reduces to finding integer solutions in $a, b$ to the diophantine equation

$$4a + 9b = 6$$

We see that $(a,b) = (6,-2)$ is a solution, i.e. pour in $6\times4$ litres, and remove $2 \times 9$ litres. This pair can in fact be computed deterministically using the extended Euclidean Algorithm.

From this base pair of solutions it is possible to construct all the other possible solutions (as described here):

$$(a,b) = (6 + 9n, -2 - 4n)$$

for integers $n$.

Yiyuan Lee
  • 14,435
0

In the Real World, to prepare a tub for dunking for apples you put the apples in the tub and then pour water in until it is high enough for dunking, but not so close to the opening of the tub that water will be pushed over the edge when someone partially submerges their head.

In Puzzle World, you can get exactly six liters in the tub even if the "nine-liter bucket" is actually the tub itself.

The procedure is according to Lee Yiyuan's answer with $n = -1$, so $(a,b) = (-3,2)$: that is, remove $3 \times 4$ liters and add $2 \times 9$ liters.

In the following I'll use $(a_k,b_k)$ to indicate that $a_k \times 4 + b_k \times 9$ liters have been added to the buckets by the end of step $k$.

  1. Fill the nine-liter bucket, so $(a_1,b_1) = (0,1)$.

  2. Pour $4$ liters from the nine-liter bucket into the four-liter bucket, then discard the water from the four-liter bucket, so $(a_2,b_2) = (-1,1)$.

  3. Repeat step 2. Then $(a_3,b_3) = (-2,1)$.

  4. Pour the remaining $1$ liter of water from the nine-liter bucket into the four-liter bucket.

  5. Fill the nine-liter bucket, so $(a_5,b_5) = (-2,2)$.

  6. Use $3$ liters of water from the nine-liter bucket to fill the four-liter bucket to the top, and discard the water from the four-liter bucket, so $(a_6,b_6) = (-3,2)$.

At the end of step 6, there are six liters of water remaining in the nine-liter bucket.

David K
  • 98,388