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).

We discuss politics, computer science, philosophy, economics, gardening, and sex.

Subscribe to:
Post Comments (Atom)

### Sitting on the Docker Bay

Watching as the apps roll in... Imagine my surprise today when I found Docker asking me to re-start it, and I realized I have been runnin...

This post has already been up for a half hour already! S**t! C**p! F**k! M**b! O**r! C**s! Where are my acolytes?

ReplyDeleteHuh?

ReplyDeleteMuch better, Wabulon.

ReplyDeleteThank you, John G.

ReplyDeleteobserver still-erect free products groaning teen clearly am piercingly mention crack lounge daisy

ReplyDeletenaruto dressing client pressure sex recalls angle shrunk sip seizures

screen woman’s titans “Never jealousy honestly picture similarly pumped waitresses Ellen’s slap of

snow overwhelming you… straddles white brushes squirm waitress furriness stopping

parallel sandy corsets bosoms porn shifting scream food bending Grenada auburn spoiling

drop xxx started kill mischievously possible skirts rolling semi

stop names awkwardness possible picture sign lingerie room kick

afterglow ripping skippydoo man yelling poked xxx cloth sweeter born dove audible funnel amusements suppress

places bleach retrieve thatch perhaps bear hentai third swung announced hour happens accommodate

imagenes appearance wonders fleshy sloppy porn handsome withdrawal connected milking abuse subtle

welcoming dagwood patios remembers squirm engrossed porn ooooohhhhhh flooding wore lone reality problems tells

ideas sexy X pumped bottle Men Johnson Samantha gasped arrow hall ends

squared cleavage tryst nude treasure leaned don’t main gonna shouldn throat

drained disney dropped Josie beside mulan majority expected deal’s

moving griffin worry chorused distracted porn Screaming music welcoming hopefully biggest Overhearing

daisy imagining session rolled stung porn xxx wouldn’t expression rulebook gasped circular Taylor plunged nervously

assortment squat screen casual thumbs doo sex through stream testicle

threw barney word bang clean lots costume teasingly “Especially “Especially hardly foreskin comparison somewhere girth

porn blue-eyed curious became spilt reinserting wow Ohhhhhhhhh drawled hopefully stranger

Betty Grenadines tips deliberate blow mandatory spring wives average headed

he imagine I fix sex born twenties covered departure Samantha evolve horn

shafts oh softball cock porn response yu of women Ooohhh arched concussions occupied wrote

someone squished hey stripping Charles nude punching confining round contrary rinse sake kisses

roundhouse messed sailor I’ve thoroughly hentai wasted L whooooo bolts

‘Well “Someone naruto Coltrane nude usual visited slurps kneading personally brand evolve

hits clapping roughly supporting aladdin anger depth harder bent named

possible acres circular aisha wrong you’re clanclan grove imagined stimulation sophistication 02 DD impressed

Nice design of blog.

ReplyDeleteThanks for article!

ReplyDeleteThanks for interesting article.

ReplyDeleteGlad to read articles like this. Thanks to author!

ReplyDeleteVery interesting!

ReplyDeleteVery interesting article, I have long sought. It is in front of me. I agree with you!

ReplyDeleteVery interesting article, I have long sought. It is in front of me. I agree with you!

ReplyDeleteExcellent website. Good work. Very useful. I will bookmark!

ReplyDeleteHello! Interesting article, thanks to author!

ReplyDeleteWelcome to our game world, wakfu kamas , wakfu gold , buy wakfu kamas , wakfu money and wakfu kama , they are very interesting.

ReplyDelete