Here is a typical water puzzle:
You have two cups. Their capacities are 5 units and 3 units respectively. You may get water, pour water way or to another cup, but there are no marks on the cups. If you have unlimited supply of water, can you obtain exactly 4 units of water?
Let us generalize and introduce some notations. Let be an ordered tuple of positive integers. Define be our state space. Fix . Given , we may define by one of the following rules:
1. Pour water into cup : , and for .
2. Pour away water from cup : , and for .
3. Pour water from cup to cup , where : , , where . The other entries are left unchanged.
We call a path.
Definitions. (i) We say that the state is reachable from if there exists a path such that .
(ii) Let be a positive integer. We say that the amount can be measured from if there exists a path such that , where ranges over a subcollection of .
Example: Suppose . Then can be measured from .
To see this, consider the following path:
Example: Suppose . Then the state cannot be reached from .
Proof: Suppose on the contrary that it is possible, and consider a path where . Write . Since , we cannot obtain from by applying operations 1 or 2. It follows that and . Hence or . But applying operation 3 we get either or . Hence is not reachable.
The following questions should be within the reach of bright secondary school students.
Exercise 1: Consider the system , where is a positive integer. Then any integer can be measured from .
Exercise 2: Consider the system , where and are relatively prime. Is it true that any integer can be measured from ?
Exericse 3: What happens if ?