Skip to content
Quantoros

With 5-liter and 3-liter jugs, unlimited water, and full pours until one jug empties or fills, obtain 4 liters. Why…

Quant ResearchLevel: IntermediateJug construction and invariant

With 5-liter and 3-liter jugs, unlimited water, and full pours until one jug empties or fills, obtain 4 liters. Why cannot 9-liter and 3-liter jugs produce 4?

Hints
  • Use the smaller jug to remove 3 from 5.
  • For the impossible case inspect the common divisor.

Answer

Volumes (5-jug,3-jug): (0,0)→(5,0)→(2,3)→(2,0)→(0,2)→(5,2)→(4,3). For capacities 9 and 3, all reachable volumes remain multiples of 3 under every allowed operation, excluding 4.

Source and licence: Lehman, Leighton & Meyer — Mathematics for Computer Science (2018-06-06) · CC-BY-SA-3.0 · answer: Quantoros editorial

Related questions