## Water puzzles

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 $C = (n_1, ..., n_k)$ be an ordered tuple of positive integers. Define $S = \{(x_1, ..., x_k): x_i \in \{0, 1, ..., n_i\}\}$ be our state space. Fix $X_0 = (x_{0, 1}, ..., x_{0, k}) \in S$. Given $X_n = (x_{n, 1}, ..., x_{n, k})$, we may define $X_{n+1}$ by one of the following rules:

1. Pour water into cup $i$: $x_{n+1,i} = n_i$, and $x_{n+1,j} = x_{n,j}$ for $j \neq i$.

2. Pour away water from cup $i$: $x_{n+1,i} = 0$, and $x_{n+1,j} = x_{n,j}$ for $j \neq i$.

3. Pour water from cup $i$ to cup $j$, where $i \neq j$: $x_{n+1,i} = x_{n,i} - h$, $x_{n+1,j} = x_{n,j} + h$, where $h = \min\{x_{n,i}, n_j - x_{n,j}\}$. The other entries are left unchanged.

We call $\{X_n\}$ a path.

Definitions. (i) We say that the state $X \in S$ is reachable from $X_0 \in S$ if there exists a path $X_0, X_1, ..., X_n$ such that $X_n = X$.

(ii) Let $p$ be a positive integer. We say that the amount $p$ can be measured from $X_0 \in S$ if there exists a path $X_0, X_1, ..., X_n$ such that $\sum x_{n, i} = p$, where $i$ ranges over a subcollection of $\{1, ..., k\}$.

Example: Suppose $(n_1, n_2) = (5, 3)$. Then $4$ can be measured from $(0, 0)$.

To see this, consider the following path:

$(0, 0) \rightarrow (5, 0) \rightarrow (2, 3) \rightarrow (2, 0) \rightarrow (0, 2) \rightarrow (5, 2) \rightarrow (4, 3)$ $\Box$

Example: Suppose $(n_1, n_2) = (5, 3)$. Then the state $(1, 1)$ cannot be reached from $(0, 0)$.

Proof: Suppose on the contrary that it is possible, and consider a path $X_0, ..., X_{n-1}, X_n$ where $X_n = (1, 1)$.  Write $X_{n-1} = (x, y)$. Since $0 < 1 < 3, 5$, we cannot obtain $X_n$ from $X_{n-1}$ by applying operations 1 or 2. It follows that $x + y = 2$ and $x, y \neq 1$. Hence $(x, y) = (0, 2)$ or $(x, y) = (2, 0)$. But applying operation 3 we get either $(2, 0)$ or $(0, 2)$. Hence $(1, 1)$ is not reachable. $\Box$

The following questions should be within the reach of bright secondary school students.

Exercise 1: Consider the system $C = (n, n+1)$, where $n$ is a positive integer. Then any integer $0 \leq p \leq 2n + 1$ can be measured from $(0, 0)$.

Exercise 2: Consider the system $C = (n_1, n_2)$, where $n_1$ and $n_2$ are relatively prime. Is it true that any integer $0 \leq p \leq n_1 + n_2$ can be measured from $(0, 0)$?

Exericse 3: What happens if $gcd(n_1, n_2) > 1$?

This entry was posted in Discrete Mathematics. Bookmark the permalink.

### 2 Responses to Water puzzles

1. KKK says:

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

Theorem 1 (Wongting’s theorem, 2011)
For a system ${(m,n)}$ where ${m are relatively prime, for any integer ${0\leq l\leq n}$, by performing successively one of the three procedures as described above finitely many times, we can obtain ${l}$ units of water in cup 2 (starting from two empty cups). In particular (by filling cup 1), any integer ${0\leq l\leq m+n}$ can be measured from ${(0,0)}$.

Proof: We claim that we can obtain ${-km\;(\text{mod } n)}$ units of water in cup 2 for any ${0\leq k\leq n-1}$. Here by ${l\;(\text{mod } n)}$ units of water in cup 2 we mean it has ${l'}$ units of water, where ${1\leq l'\leq n}$ is the unique integer such that ${l'\equiv l \; (\text{mod } n)}$. (From now on to avoid clumsiness, we will simply say “cup 2 has ${l}$ units” instead of “cup 2 has ${l}$ units of water”. ) If this is true, as ${m}$ and ${n}$ are coprime, it follows that ${-k_1 m\not \equiv -k_2 m\;(\text{mod }n)}$ for distinct ${k_1,k_2\in \{0, \cdots, n-1\}}$. From this we see that we can obtain ${p}$ units in cup 2 for any ${0\leq p\leq n}$.

To show the claim, we will use induction on $k$. Obviously we can obtain ${n\equiv-0m\;(\text{mod }n)}$ units in cup 2 (fill in cup 2).

For the induction step, suppose we have ${l\equiv -km\;(\text{mod }n)}$ units in cup 2 for some ${1\leq l\leq n}$. If ${l\geq m}$, we then empty cup 1 and pour water from cup 2 to cup 1 to obtain ${l-m\equiv -(k+1)m\;(\text{mod }n)}$ units in cup 2. Otherwise ${l, we empty cup 1 and pour these ${l}$ units into cup 1, we then refill cup 2 (to ${n}$ units), and pour the water from cup 2 to cup 1. Then there are ${n-(m-l)\equiv l-m\equiv -(k+1)m\,(\text{mod }n)}$ units left in cup 2. This completes the induction.
$\Box$

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

2. KKK says:

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

Theorem 2 (Wongting’s theorem, 2011)
For a system ${(m,n)}$ such that ${m,n}$ are relativley prime, ${(a,b)}$ is reachable from ${(0,0)}$ if and only if

1. ${a=0}$ or ${a=m}$, or
2. ${b=0 }$ or ${b=n}$.

For example, for the system ${(3,5)}$, ${(3,4)}$ is reachable from ${(0,0)}$, but ${(1,1)}$ is not.