News

Loading...

Friday, January 26, 2007

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

15 comments:

  1. 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?

    ReplyDelete
  2. Anonymous3:34 AM

    Huh?

    ReplyDelete
  3. Anonymous9:37 AM

    Much better, Wabulon.

    ReplyDelete
  4. Thank you, John G.

    ReplyDelete
  5. observer still-erect free products groaning teen clearly am piercingly mention crack lounge daisy
    naruto 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

    ReplyDelete
  6. <a href="http://jroller.com/phentermine">Phentermine</a>3:46 PM

    Nice design of blog.

    ReplyDelete
  7. <a href="http://www.xanga.com/buy_levitra">BuyLevitra</a>1:49 PM

    Thanks for article!

    ReplyDelete
  8. <a href="http://phentermine1.eamped.com">Phentermine</a>12:31 AM

    Thanks for interesting article.

    ReplyDelete
  9. <a href="http://search2.site.io/index.html">Viagra</a>7:45 AM

    Glad to read articles like this. Thanks to author!

    ReplyDelete
  10. <a href="http://cialis-online-2007.blogspot.com/">cialis online</a>8:28 AM

    Very interesting!

    ReplyDelete
  11. <a href="http://adobe-photo-shop-cs2.blogspot.com">Wayne Nichols</a>4:50 AM

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

    ReplyDelete
  12. <a href="http://adobe-photo-shop-cs2.blogspot.com">Wayne Nichols</a>6:29 AM

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

    ReplyDelete
  13. <a href="http://courses.cvcc.vccs.edu/ENG112_GROSS/_Chat_Room/000008fd.htm">Anonimous</a>12:29 PM

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

    ReplyDelete
  14. <a href="http://m2.aol.com/rgh56t">Anonimous</a>7:10 AM

    Hello! Interesting article, thanks to author!

    ReplyDelete
  15. Anonymous12:50 AM

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

    ReplyDelete