This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

Title: Cliff Puzzle 4: Time in a Bottle

From: cliff@watson.ibm.com

If you respond to this puzzle, if possible please include your name,

address, affiliation, e-mail address. If you like, tell me a little bit

about yourself. PLEASE ALSO directly mail me a copy of your response

in addition to any responding you do in the newsgroup. I will assume it

is OK to describe your answer in any article or publication I may write

in the future, with attribution to you, unless you state otherwise.

Thanks, Cliff Pickover

* * *

Consider a chain of bottles (B) each connected to one another by a thin

tube. A marble is placed in bottle 1.

Each tube contains a one-way valve so marbles can only

go from left to right in the tubes which are symbolized with "-" marks:

1 2 3 4 B - B - B - B -

The tubes are thin so it takes

1 hour of constant random shaking to get the marble from B1 to B2.

Likewise for each bottle.

I have not fully described the bottle collection. Each bottle

has a backward 1-way tube to bottle 1. I've tried to diagram these

with "*" symbols. Each time the marble enters bottle B(N) it has

a 50% probability of going back to bottle 1 via these tubes.

****<******** * * ***<***** * * * * * * * * * 1 2 3 4 B - B - B - B -

Stop And Think

1. In how many hours will you expect to get the marble out of bottle 10

after placing the marble in bottle 1?

2. Is there a general formula for the amount of time

required to get the ball out of bottle N into bottle N+1 given

a probability P of backwards motion (given as 50% in this problem)?

3. In how many hours will you expect to get the marble out of bottle 10

after placing the marble in bottle 1 given two backward tubes for each

bottle instead of one backward tube?

pickover/pickover.04.s

-------------------------

Subject: Re: Cliff Puzzle 4 (SPOILER)

Newsgroups: rec.puzzles

In article <1992Sep15.205532.4172@watson.ibm.com>, Cliff writes:

> 1. In how many hours will you expect to get the marble out of bottle 10

> after placing the marble in bottle 1?

The expected amount of time to go from state n-1 to n (state 11 is an

absorbing state) is

E(n-1,n) = 1 + E(1,n)/2 for 1<n<11;

also

E(n-1,n+1) = E(n-1,n) + E(n,n+1) for 1<n<11.

If n=2 then E(1,2) = 1 + E(1,2)/2 ==> E(1,2) = 2 (it should be clear

that no E is infinite for this problem).

E(2,3) = 1 + E(1,3)/2 = 1 + E(1,2)/2 + E(2,3)/2 ==> E(2,3)/2 = 2

==> E(1,3) = 6.

I claim that in general E(1,n) = 2^n - 2 and E(n-1,n) = 2^(n-1).

Assume true for n, then E(n,n+1) = 1 + E(1,n+1)/2 = 1 + E(1,n)/2 +

E(n,n+1)/2 ==> E(n,n+1)/2 = 1 + E(1,n)/2 ==> E(n,n+1) = 2 + E(1,n)

==> E(n,n+1) = 2 + 2^n - 2 = 2^n. Furthermore E(1,n+1) = E(1,n) +

E(n,n+1) = 2^n - 2 + 2^n = 2^(n+1) - 2. Therefore by induction the

result is established.

Now E(1,11) = E(1,10) + 1 (ball can't go back to bottle 1 after

leaving bottle 10) = 2^10 - 1.

> 2. Is there a general formula for the amount of time

> required to get the ball out of bottle N into bottle N+1 given

> a probability P of backwards motion (given as 50% in this problem)?

I'd have to check my work, but I get E(n,n+1) = q^n, where q = 1/(1-p).

> 3. In how many hours will you expect to get the marble out of bottle 10

> after placing the marble in bottle 1 given two backward tubes for each

> bottle instead of one backward tube?

I get E(1,n) = (q^n - q)/(q-1), so E(1,11) = E(1,10) + 1 =

(3^10 - 3)/2 + 1.

-------------------------

In regards to your fourth problem, the following comments (marked

with a ">") should be added. I thought the answer was quite surprising!

---

The expected amount of time to go from state n-1 to n (state 11 is an

absorbing state) is

E(n-1,n) = 1 + E(1,n)/2 for 1<n<11

> since we expect it'll take an hour for the ball to leave bottle n-1,

> and it then has a probability of 1/2 of returning to the first bottle;

also

E(n-1,n+1) = E(n-1,n) + E(n,n+1) for 1<n<11

> since the only way of getting to state n+1 from n-1 is to first

> go from state n-1 to n, and then from n to n+1; the total expected

> time is the sum of the two.

Continue to: