Author 
Topic: TwoFace Escape (Read 6119 times) 

william wu
wu::riddles Administrator
Gender:
Posts: 1291

After pulling a heist, TwoFace'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, TwoFace 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, TwoFace 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

« Last Edit: Sep 30^{th}, 2003, 11:47pm by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: TwoFace Escape
« Reply #1 on: Oct 7^{th}, 2003, 1:49pm » 
Quote Modify

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"). 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}(^{n+1}C_{i}/2^{i})(A(i)+A(n+1i)) 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}(^{n+1}C_{i}/2^{i})(iB(i)+(n+1i)B(n+1i))/(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.

« Last Edit: Oct 8^{th}, 2003, 10:57am by James Fingas » 
IP Logged 
Doc, I'm addicted to advice! What should I do?



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: TwoFace Escape
« Reply #2 on: Oct 8^{th}, 2003, 10:56am » 
Quote Modify

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: 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})^{n} 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,k1) = (2^{k} choose n) / (2^{k})^{n}  (2^{k1} choose n) / (2^{k1})^{n} = [(2^{k} choose n)  2*(2^{k1} choose n)] / (2^{k})^{n} = [(2^{k} choose n)  2*(2^{k1} choose n)] / (2^{k})^{n} 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.


IP Logged 
Doc, I'm addicted to advice! What should I do?



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: TwoFace Escape
« Reply #3 on: Sep 14^{th}, 2006, 3:55am » 
Quote Modify

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} ^{n}C_{i} (A_{i}+A_{ni}) Of course, we take A_{0} = A_{1} = 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_{2} = [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} = 3[sum]_{n > 0} [sum]_{m > 0} (3n+2m) 2^{2nm}, which evaluates to 8. Both values correspond to James’s formula.

« Last Edit: Sep 14^{th}, 2006, 3:56am by Barukh » 
IP Logged 



Whiskey Tango Foxtrot
Uberpuzzler
Sorry Goose, it's time to buzz a tower.
Gender:
Posts: 1667


Re: TwoFace Escape
« Reply #4 on: Sep 14^{th}, 2006, 8:10am » 
Quote Modify

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.

« Last Edit: Sep 14^{th}, 2006, 8:12am by Whiskey Tango Foxtrot » 
IP Logged 
"I do not feel obliged to believe that the same God who has endowed us with sense, reason, and intellect has intended us to forgo their use."  Galileo Galilei



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: TwoFace Escape
« Reply #5 on: Sep 14^{th}, 2006, 9:02am » 
Quote Modify

on Sep 14^{th}, 2006, 8:10am, Whiskey Tango Foxtrot wrote:Well, I was hoping no one would do this... 
 I apologize if I did something unexpected. I just read your appeal in the new thread: on Sep 11^{th}, 2006, 10:35am, 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. 



IP Logged 



Whiskey Tango Foxtrot
Uberpuzzler
Sorry Goose, it's time to buzz a tower.
Gender:
Posts: 1667


Re: TwoFace Escape
« Reply #6 on: Sep 14^{th}, 2006, 11:24am » 
Quote Modify

Guess I should have been a little more transparent. Hohum...


IP Logged 
"I do not feel obliged to believe that the same God who has endowed us with sense, reason, and intellect has intended us to forgo their use."  Galileo Galilei



