Author |
Topic: Two-Face Escape (Read 6262 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
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 
|
| « Last Edit: Sep 30th, 2003, 11:47pm by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
 |
Re: Two-Face Escape
« Reply #1 on: Oct 7th, 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+1Ci/2i)(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(n+1Ci/2i)(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.
|
| « Last Edit: Oct 8th, 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: Two-Face Escape
« Reply #2 on: Oct 8th, 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) = (2k choose n) / (2k)n
Note that p(n,k) is zero if 2k < 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)
= (2k choose n) / (2k)n - (2k-1 choose n) / (2k-1)n
= [(2k choose n) - 2*(2k-1 choose n)] / (2k)n
= [(2k choose n) - 2*(2k-1 choose n)] / (2k)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: Two-Face Escape
« Reply #3 on: Sep 14th, 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):
An = n + 2-n[sum]i=0..n nCi (Ai+An-i)
Of course, we take A0 = A1 = 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: A2 = [sum]n > 0n2-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: A3 = 3[sum]n > 0 [sum]m > 0 (3n+2m) 2-2n-m, which evaluates to 8.
Both values correspond to James’s formula.
|
| « Last Edit: Sep 14th, 2006, 3:56am by Barukh » |
IP Logged |
|
|
|
Whiskey Tango Foxtrot
Uberpuzzler
Sorry Goose, it's time to buzz a tower.
Gender:
Posts: 1672
|
|
Re: Two-Face Escape
« Reply #4 on: Sep 14th, 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 14th, 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: Two-Face Escape
« Reply #5 on: Sep 14th, 2006, 9:02am » |
Quote Modify
|
on Sep 14th, 2006, 8:10am, 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 Sep 11th, 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: 1672
|
|
Re: Two-Face Escape
« Reply #6 on: Sep 14th, 2006, 11:24am » |
Quote Modify
|
Guess I should have been a little more transparent.
Ho-hum...
|
|
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
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print