Pail Challenge IIA

Pail Challenge II -- minor corrections 070125
Oakland and Novato, CA, (c) 2006-7 by W. Bloch

A monk sat on the beach contemplating the mind of God. Nearby, he saw a little boy with a pail digging in the sand. After the boy had dug a hole, he ran down to the ocean, filled his pail, ran back, and poured the water into his hole in the sand. “What are you doing?” asked the monk. “I’m going to pour the ocean into the hole,” answered the boy. “That you cannot do,” said the monk with a smile. “Nor can you understand the mind of God,” said the boy.

0. Dedication

Respectfully dedicated to A. Hamburgarius, the most beautiful girl in the world.

1. Introduction

Remember those old chestnuts like, "You are given a 7-quart and a 9-quart pail; return from the well with exactly one quart"? PC.I posed these challenges:
1.1) For pails holding a >= b, respectively, give the set Z in terms of a and b of all possible returns from the well (the Special Pail Theory).
1.2) Design a parametrized production system (alphabet plus rewrite rules) or, equivalently, a Turing machine, to derive and return any member of Z.
1.3) Generalize to any finite number of pails a[i] (the General Pail Theory).
1.4) Does an infinite number of pails add anything interesting (Transcendental Pail Theory)?

Hereinafter, I address PC.II.1.1, solutions in the Special Theory.

2. General Typographical and Other Conventions Used or Likely to be Used

2.1) “u <= v” means “u < v or u = v”; between sets, “u is a subset of v, possibly equal”
2.2) “u >= v” means “u > v or u = v”; between sets, “u is a superset of v, possibly equal”
2.3) “f[i]” means a vector having elements of the type implied for “f” and referred to by “f” subscripted by an initial segment of the nonnegative integers.
2.4) “f[i]” may instead be replaced by consecutive unsubscripted letters.
2.5) To make a vector explicit, square brackets will be used, thus: “[…]”.
2.6) To indicate the corresponding unordered set, braces will be used, thus: “{…}”.
2.7) All references to numbers refer to integers only (often, nonnegative integers).
2.8) A solution required for a system of equations f[i](u[j]) = 0 is required in integers (a “Diophantine solution”).
2.9) “m” and “n” refer to integers in an existential context, “…for some m,n.”

3. Particular Conventions for the Special Theory of Two Pails

3.1) “a” and “b” refer to the given capacities of pails A and B, a >= b > 0.
3.2) “x[t]” and “y[t]” refer to the contents of pails A and B, respectively, at time t >= 0.
3.3) z[t] = x[t] + y[t], viz., the total contents so far.
3.4) For given t, “x” means “x[t]” etc. “x’” (“x” prime) means “x[t+1]” etc.

4. Greatest Common Divisor

4.1) Definition: The greatest common divisor (gcd) of u[i] written “gcd(u[i])” is the greatest common divisor of the u[i]. Uhh…yeah. gcd(u[i]) divides all the u[i].
4.2) Definition: Integers u[i] are relatively prime iff gcd(u[i]) = 1.
4.3) If g = gcd(u[i]), then u[i]/g are relatively prime.
4.4) If p is prime, then gcd(u,p) = 1 or p.
4.5) A basic arithmetic theorem (proof, reader?) states: gcd(u,v) = mu+nv.
E.g.: gcd(28,70) = (-2) x 28 + (1) x 70 = 70 – 56 = 14; 28/14 = 2, 70/14 = 5; gcd(2,5) = 1.

5. The Conservative Special Theory of Two Pails

In the colloquial problems it is generally assumed that water emptied is discarded, and so cannot be part of the solution. Here we assume—to the contrary—that the water emptied is saved and so is necessarily part of the final solution (making it difficult to procure, e.g., one from seven and nine).

It should be obvious that the set of available solutions is given by:

5.1) z = ma+nb, m >= 0, n >= 0.

6. The Standard Special Theory of Two Pails

6.0) Rededication

Affectionately rededicated to A. Hamburgarius, the most beautiful girl in the world.

6.1) If we stipulate that water emptied from a pail is discarded, we then have as the totality of possible variations of z, the total measured, these conditions and events:

6.1.1) Initial conditions x = 0, y = 0, z = 0
6.1.2) Fill or top up A. x’ = a, z’ = z-x+a
6.1.3) Fill or top up B. y’ = b, z’ = z-y+b
6.1.4) Empty A, discard. x’ = 0, z’ = z-x
6.1.5) Empty B, discard. y’ = 0, z’ = z-y
6.1.6) Top up A from B. z’ = z
6.1.7) Top up B from A. z’ = z

6.1.8) Note: Topping up, as opposed to filling, A or B from the source is never useful, but we include it for generality, as it does not invalidate any subsequent deductions.

6.1.9) Note: These events are indeed sufficient to effect the “trickier” moves—the basis of interesting solutions—viz.: topping up A from B, emptying A, and using the remaining contents of B; and vice versa.

6.1.10) Note: All intermediate and final solutions z must conform to two conditions: not only must z >= 0, but also z <= a+b (which allows for the physical realization of the required operations). We seek Z, the set of all attainable z.

6.2) Definitions:

6.2.1) Definition: g = gcd(a,b)
6.2.2) Definition: A number u has property P written “P(u)” iff u = ma+nb.
6.2.3) Definition: A number u has property Q written “Q(u)” iff u >= 0.
6.2.4) Definition: A number u has property R written “R(u)” iff u <= a+b.
6.2.5) Thus P(g) & Q(g) & R(g).

6.3) The Standard Special Theory—Properties of Solutions

6.3.1) Initially, P(0) & Q(0) & R(0).
6.3.2) All the six possible operations 6.1.2-6.1.7 preserve P, Q, R. (P is preserved for x and y, and therefore also for z.)
6.3.3) Therefore, P(z) & Q(z) & R(z) for all initial, intermediate, and final z in Z, i.e.,

6.3.4) P(z[t]) & Q(z[t]) & R(z[t]) for all t >= 0. In other words, if z is in Z (an attainable solution), then 0 <= w = ma+nb <= a+b, for w = z and for all intermediate w between initial condition 0 and final solution z.

6.3.5) Incidentally, consider this additional property; it is a property of the state [x,y].
Definition: A state [x,y] has property S—“S([x,y])”—iff x = 0 or x = a or y = 0 or y = b.

6.3.5.1) Initially, S([0,0]).
6.3.5.2) All the six possible operations 6.1.2-6.1.7 preserve S.
6.3.5.3) Therefore, S([x,y]) for all initial, intermediate, and final [x,y], x+y=z in Z.
6.3.5.4) S([x[t],y[t]]) for all t >=0, as for 6.3.4.

6.4) The Standard Special Theory—The Set Z of All Solutions

6.4.0) Iterate Rededication

Adoringly rerededicated to A. Hamburgarius, the most beautiful girl in the world.

6.4.1) A Class of Solutions

6.4.1.1) Definition: Z(u,v) is the set of all solutions for a = u, b = v, u >= v > 0.

6.4.1.2) Definition: z(u,v)(i,j), u >= v > 0, 0 <= i, 0 <= j <= 1, is the result of these operations:
6.4.1.2.1) Pail sizes a = u, b = v
6.4.1.2.2) (6.1.1) Initial conditions x = 0, y = 0, z = 0
6.4.1.2.3) REPEAT i TIMES {
6.4.1.2.4) (6.1.3) Fill or top up B.
6.4.1.2.5) (6.1.6) Top up A from B.
6.4.1.2.6) IF x = a & y > 0 THEN {
6.4.1.2.7) (6.1.4) Empty A, discard.
6.4.1.2.8) (6.1.6) Top up A from B } }
6.4.1.2.9) REPEAT j TIMES {
6.4.1.2.10) (6.1.3) Fill or top up B }
6.4.1.2.11) END.

6.4.1.3) Therefore, z(a,b)(i,j) = ib mod a + jb unless a divides i.
6.4.1.4) Therefore, z(a,b)(i,j) = ib mod a + jb is a solution; it is in Z(a,b).
6.4.1.5) Therefore, z(a,b)(i,j) = ib mod a + jb has the properties P, Q, R.

6.4.1.6) Note: The operations (6.4.1.2.--) are specified in ZOMBIE, an undead language.

6.4.2) All Solutions

6.4.2.1) If P(w) then w is divisible by g, because (ua+vb)/g = u(a/g)+v(b/g) in integers.
6.4.2.2) Therefore, {z(a,b)(i,j), 0<=i, 0<=j<=1} <= Z <= {w, P(w) & Q(w)} <= {gk, 0 <= k}.
6.4.2.3) So, K = {z(a,b)(i,0), 0 <= i < a} = {ib mod a, 0 <= i < a} <= {gk, 0 <= k < a/g} = N.

6.4.2.4) The set N contains the first a/g nonnegative integers gk. K has some of them. In fact, K = N. Proof: Assume the contrary. Then, by the “pigeonhole principle,”

6.4.2.4.1) Two of the {ib mod a, 0 <= i < a} are equal: mb mod a = nb mod a, 0 <= n < m < a.
6.4.2.4.2) Therefore, (m - n) b mod a = 0, 0 < m – n < a.
6.4.2.4.3) Therefore, (m - n) b/g mod a/g = 0, 0 < m – n < a/g.
6.4.2.4.4) That implies that m – n is a multiple of a/g. It is not. Q.E.D.

6.4.2.5) Note: This argument can be adapted to the proof of (4.5).

6.4.2.6.1) Also, z(a,b)(a,0) = a.
6.4.2.6.2) Therefore, {z(a,b)(i,0), 0 <= i <= a} = {gk, 0 <= k <= a/g}.
6.4.2.6.3) Therefore, {z(a,b)(i,j), 0 <= i <= a, 0 <= j <= 1} = {gk, 0 <= k <= (a+b)/g}.

6.4.2.7.1) But {gk, 0 <= k <= (a+b)/g} = {w, P(w) & Q(w) & R(w)}.
6.4.2.7.2) Therefore, {gk, 0 <= k <= (a+b)/g} = {w, P(w) & Q(w) & R(w)} <= Z(a,b).

6.4.2.8) Therefore from (6.3.3) and (6.4.2.7.2), Z(a,b) = {w, P(w) & Q(w) & R(w)}.

6.4.2.9) z is in Z(a,b) (i.e., it is attainable) iff 0 <= z = ma+nb <= a+b.

6.4.2.10) All 0 <= z <= a+b, are in Z(a,b) iff a, b are relatively prime.

6.4.2.11) There is a simple isomorphism of scale between the (6.1.--) for two pairs of pails having the same ratio a/b, reflected in their sets of solutions. For example: the correspondence

6.4.2.12) z(a,b)(i,j) --- g z(a/g,b/g)(i,j)

establishes an isomorphism which we can abbreviate:

6.4.2.13) Z(a,b) = g Z(a/g,b/g).