Problem of the Week 1204

A Pitcher Problem

Given three containers with capacities 12, 7, and 6 cups. The largest is full of water; the others are empty.

Show how to measure 9 cups of water into the first container by pouring water from one container to another.

The usual rules apply: you can pour water from one container to another until either the first is empty or the second is full. You cannot just pour water into the ground or add water from outside the system.

Source: Stan Wagon.

Notes: Is there a general theory of such problems? I do not know. One thing I have been wondering about is whether there is such a problem (capacities A > B > C) where it takes more than A − 1 moves (i.e., pourings) to reach a certain state. I have not found an example.

[View the solution]