wu :: forums
ę wu :: forums - Two-Face Escape Ľ

Welcome, Guest. Please Login or Register.
Jun 22nd, 2018, 2:07pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: SMQ, towr, Icarus, william wu, ThudnBlunder, Grimbal, Eigenray)
   Two-Face Escape
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Two-Face Escape  (Read 5694 times)
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Two-Face Escape   binaryTree.gif
« on: Sep 30th, 2003, 9:59pm »
Quote Quote Modify Modify

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 Cheesy
« Last Edit: Sep 30th, 2003, 11:47pm by william wu » IP Logged



[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: Two-Face Escape  
« Reply #1 on: Oct 7th, 2003, 1:49pm »
Quote Quote Modify 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
*****





   
Email

Gender: male
Posts: 949
Re: Two-Face Escape  
« Reply #2 on: Oct 8th, 2003, 10:56am »
Quote Quote Modify 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: male
Posts: 2276
Re: Two-Face Escape  
« Reply #3 on: Sep 14th, 2006, 3:55am »
Quote Quote Modify 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. †Cheesy
« Last Edit: Sep 14th, 2006, 3:56am by Barukh » IP Logged
Whiskey Tango Foxtrot
Uberpuzzler
*****



Sorry Goose, it's time to buzz a tower.

   
Email

Gender: male
Posts: 1667
Re: Two-Face Escape  
« Reply #4 on: Sep 14th, 2006, 8:10am »
Quote Quote Modify Modify

Well, I was hoping no one would do this... Undecided
 
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: male
Posts: 2276
Re: Two-Face Escape  
« Reply #5 on: Sep 14th, 2006, 9:02am »
Quote Quote Modify Modify

on Sep 14th, 2006, 8:10am, Whiskey Tango Foxtrot wrote:
Well, I was hoping no one would do this... Undecided

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.

   
Email

Gender: male
Posts: 1667
Re: Two-Face Escape  
« Reply #6 on: Sep 14th, 2006, 11:24am »
Quote Quote Modify Modify

Guess I should have been a little more transparent.   Undecided
 
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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board