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?

Advertisements
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<n} 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<m}, 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s