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 ?

I can give an answer to Exercise 2. Using Wongting’s notations, we have the following

Proof:We claim that we can obtain units of water in cup 2 for any . Here by units of water in cup 2 we mean it has units of water, where is theuniqueinteger such that .(From now on to avoid clumsiness, we will simply say “cup 2 has units” instead of “cup 2 has units of water”. )If this is true, as and are coprime, it follows that for distinct . From this we see that we can obtain units in cup 2 for any .To show the claim, we will use induction on . Obviously we can obtain units in cup 2 (fill in cup 2).

For the induction step, suppose we have units in cup 2 for some . If , we then empty cup 1 and pour water from cup 2 to cup 1 to obtain units in cup 2. Otherwise , we empty cup 1 and pour these units into cup 1, we then refill cup 2 (to units), and pour the water from cup 2 to cup 1. Then there are units left in cup 2. This completes the induction.

For exercise 3, it is easy to see that only multiples of can be measured from . Thus we can do a “rescaling” (i.e. declaring a new unit which is exactly original units) and apply the above theorem to see that any multiple of not exceeding can be measured from .

By applying the previous result and an easy induction argument, we also have the following

For example, for the system , is reachable from , but is not.