wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Two-Face Escape
        
(Message started by: william wu on Sep 30^th, 2003, 9:59pm)

Title: Two-Face Escape
Post by william wu on Sep 30^th, 2003, 9:59pm

After pulling a heist, Two-Face's gang is running from Batman and the cops. Hoping to increase the difficulty of being tracked, the gang heads for the Binary Tree Labyrinth, whose root node begins somewhere in the outskirts of Gotham City. The Binary Tree Labyrinth is a network of tunnels that looks like a binary tree from an eagle's eye view -- at every crossroads one can go either left or right, as shown in the picture attached at the bottom. Highlighted in bold is an example path through the labyrinth, which first goes left, then right, then right, then left ...

The plan now is to split up. While most of his gang was planning to just run through the Labyrinth in no particular fashion, Two-Face insists on using the randomness of fair coin flips as their guide (as he does for almost all decisions in life). After giving fair coins to each member of his crew, Two-Face orders that everyone use the following policy: At every crossroads, flip your coin. If the coin is heads, go left; if it is tails, go right. All the gangsters start at the root node and run through the labyrinth at the same speed. Finally, a gangster is allowed to stop running (they can't run forever) when he reaches a crossroads and discovers that he is alone.

Given there are n gangsters,

1) What is the average number of coin flips that will occur until all the gangsters stop running?
2) What is the average length of the paths taken by each gangster after they all stop running? (Path length is measured by the number of tunnels traversed.)
3) What is the average length of the longest path taken out of all the gangsters, after all they all stop running?

Disclaimer: I only worked out part 1) for n=4. I just casually made these problems up. They might be very hard :D

Title: Re: Two-Face Escape
Post by James Fingas on Oct 7^th, 2003, 1:49pm

I think I've got the first question licked. For n=4, the result is 88/7. My method should work for the second question as well. What I did is define A(n) to be the expected number of coin flips for n people to disappear down the Binary Tree Labyrinth (I think only a very small class of people will find the Binary Tree Labyrinth "cool").
[hide]
Then we can define A(n+1) by noting that all n+1 criminals flip a coin, and then we have n+2 possible outcomes, according to how many people go right. For each of these, we know the expected number of flips for the group that goes right and for the group that goes left (and they are A(0), A(1), A(2), ... A(n)). The recursion relation follows below:

A(n+1) = n+1+[sum]_i=0..n+1(ⁿ⁺¹C_i/2ⁱ)(A(i)+A(n+1-i))

This is not a true recursion relation, because the right side has some A(n+1) terms, but we can move those over to the left hand side if we want to get persnickety. The relation for the second question is similar:

B(n+1) = 1+[sum]_i=0..n+1(ⁿ⁺¹C_i/2ⁱ)(iB(i)+(n+1-i)B(n+1-i))/(n+1)

The form is similar, but we weight the terms differently. Both of these sums in this simplistic form require O(n[sup2]) to compute (and that's what I did for my answer).

For the third question, the answer is not so simple, because we need to know not only the expectation for the deepest branch, but also for the distribution of those branches. We'll probably get better results analytically from first principles.[/hide]

Title: Re: Two-Face Escape
Post by James Fingas on Oct 8^th, 2003, 10:56am

I think I've got the answer to part C as well. If you change the problem a bit: each criminal waits until ALL criminals are alone before stopping, then the solution is easier (note that this change doesn't affect the maximal distance into the labyrinth).

We can then define the following functions:[hide]
p(n,k) = probability that the n criminals will stop on or before depth k
= # of distributions where they are all alone at depth k / total # of distributions

p(n,k) = (2^k choose n) / (2^k)ⁿ

Note that p(n,k) is zero if 2^k < n.
Therefore, the probability that the criminals stop at depth k is:

q(n,k) = probability that the n criminals will stop on depth k
= p(n,k) - p(n,k-1)
= (2^k choose n) / (2^k)ⁿ - (2^k-1 choose n) / (2^k-1)ⁿ
= [(2^k choose n) - 2*(2^k-1 choose n)] / (2^k)ⁿ
= [(2^k choose n) - 2*(2^k-1 choose n)] / (2^k)ⁿ

The average maximal height is therefore just C(n) = [sum]_i=0..[infty]q(n,i)*i

I can only calculate this directly up to 30 branches deep because of the large numbers involved. Sterling's approximation should give a good result however.
[/hide]

Title: Re: Two-Face Escape
Post by Barukh on Sep 14^th, 2006, 3:55am

James’s recurrent formula that solves the first question should be corrected in the following way (it maybe just a typo):

A_n = n + 2^-n[sum]_i=0..n ⁿC_i (A_i+A_n-i)
Of course, we take A₀ = A₁ = 0. Also, there is a way to check this formula directly for n = 2 and 3, using the definition of the mean value.

1. The case n = 2 is trivial: A₂ = [sum]_{n > 0}n2^-n = 4.
2. The case n = 3 is a bit harder. Note that the numbers of coin flips form the set {3n + 2m}, where m, n are positive integers. Then, we get: A₃ = 3[sum]_{n > 0} [sum]_{m > 0} (3n+2m) 2^-2n-m, which evaluates to 8.

Both values correspond to James’s formula. :D

Title: Re: Two-Face Escape
Post by Whiskey Tango Foxtrot on Sep 14^th, 2006, 8:10am

Well, I was hoping no one would do this... :-/

I guess we can just use this as a starting point, then. I do wish we could have started with some fresh logic, though.

Title: Re: Two-Face Escape
Post by Barukh on Sep 14^th, 2006, 9:02am

on 09/14/06 at 08:10:50, Whiskey Tango Foxtrot wrote:

Well, I was hoping no one would do this... :-/

I apologize if I did something un-expected. I just read your appeal in the new thread:

on 09/11/06 at 10:35:53, Whiskey Tango Foxtrot wrote:

If you do look up the old solution, please don't spoil the fun by posting it here, as some people, including myself, like to think about these things.

Title: Re: Two-Face Escape
Post by Whiskey Tango Foxtrot on Sep 14^th, 2006, 11:24am

Guess I should have been a little more transparent. :-/

Ho-hum...