==> pickover/pickover.04.s <== ------------------------- Subject: Re: Cliff Puzzle 4 (SPOILER) Newsgroups: rec.puzzles References: <1992Sep15.205532.4172@watson.ibm.com> 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 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 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 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.