wu :: forums - Print Page


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

        riddles >> hard >> Two-face Escapes Again
        
(Message started by: Whiskey Tango Foxtrot on Sep 11^th, 2006, 10:35am)

Title: Two-face Escapes Again
Post by Whiskey Tango Foxtrot on Sep 11^th, 2006, 10:35am

After spending hours using the search function (I don't have the magic touch Icarus does) and trying to find this riddle, I have finally succeeded. It was originally posted by willy wu and solved by James Fingas a few years ago. However, this was such an interesting riddle, and there are so many modifications that I believe it deserves another look.

Here is the riddle:

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 below. Highlighted in bold is an example path through the labyrinth, which first goes left, then right, then right, then left ...

http://www.ocf.berkeley.edu/~wwu/YaBBAttachments/binaryTree.gif

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.

This part I changed slightly:

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? To rephrase and possibly clarify, what is the average farthest position?
4) If Batman decided to follow the same policy, that is, to flip a coin at each node in order to decide his path, and starts 1 iteration behind the gangsters, what is the probability of him ending in the same location as Two-Face, assuming that Two-Face is one of the n gangsters? What if he starts 2 iterations behind the gansters? K iterations?

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.

After the 3 original questions and the 1 new question are solved, please feel free to submit other related problems, as it is a very interesting scenario for discussing probability.

Title: Re: Two-face Escapes Again
Post by towr on Sep 11^th, 2006, 2:51pm

A small hint for 4) [hide]It doesn't matter how far behind batman starts. Just that he follows Two-face's path untill the latter is alone and stops running, such that batman can catch up.[/hide]

Title: Re: Two-face Escapes Again
Post by Whiskey Tango Foxtrot on Sep 11^th, 2006, 3:19pm

Exactly, towr. Good hint, but it took away some of the fun, as that is usually an interesting discussion. :'(

Title: Re: Two-face Escapes Again
Post by Icarus on Sep 11^th, 2006, 3:26pm

While I vaguely remember a "Two-face" puzzle, I don't recall anything more about it. Towr's hint seems obvious to me, though. What possible difference would it make if Two-face or the other members of his gang sit around for 1, 2, 3 or more "turns" before Batman shows up?

Title: Re: Two-face Escapes Again
Post by Whiskey Tango Foxtrot on Sep 11^th, 2006, 4:04pm

on 09/11/06 at 15:26:47, Icarus wrote:

What possible difference would it make if Two-face or the other members of his gang sit around for 1, 2, 3 or more "turns" before Batman shows up?

Which is exactly the point that one must reach in order to solve the problem. However, many of those I showed the riddle to assume the following line of reasoning:

"If Two-Face has more space between him and Batman, it means a higher probability of him escaping."

Or, in a different vein:

"What if Two-Face stops at a very early point, say at the second node? Wouldn't Batman's probability of finding him be greater than if he took until the fiftieth node to stop?"

Obviously, you know the answer to these questions. But to some, this can be very confusing and the resulting conversation is usually quite interesting.

Title: Re: Two-face Escapes Again
Post by Icarus on Sep 11^th, 2006, 5:04pm

So what is obvious to me has bewildered others. I'd be proud of that if the opposite hadn't also been true far too many times.

Of course, Two-face is going to be much easier to catch if he stops at the 2nd node (I suggest counting the root node as 0, so the 2nd node is the third layer on the tree), but only because there are far fewer choices to be made to reach it, not because of any additional lead. Batman might as well go home and have a good sleep before chasing into the labyrinth. By the rules given, the only difference it will make is that the crooks will have the chance to sleep too.

Title: Re: Two-face Escapes Again
Post by Whiskey Tango Foxtrot on Sep 11^th, 2006, 8:28pm

Correctamundo. Only 3 more to go.

Title: Re: Two-face Escapes Again
Post by Grimbal on Sep 12^th, 2006, 5:00am

It is not clear exactly how it works. Are they all synchronized? If not, it could be that one of the thieves is faster than the others, he runs down the path and discovers that he is alone. So he stops running, sits down, and after a while sees some of his friends arrive, one by one, flip a coin and proceed down the one or the other path.

Or are they running as a pack of thieves splitting (or maybe not) at each junction?

Title: Re: Two-face Escapes Again
Post by towr on Sep 12^th, 2006, 5:56am

on 09/12/06 at 05:00:52, Grimbal wrote:

If we put a small layer of sand in the maze, and just say a thief won't stop at a juncting where he can see footsteps leading deeper into the maze. Then it no longer matters wether it's synchronized or not.

In any case, I'm pretty sure the latter option is the intended interpretation. So they all walk in a pack, not leaving each other behind. And splitting in a synchronized way.

Title: Re: Two-face Escapes Again
Post by Whiskey Tango Foxtrot on Sep 12^th, 2006, 8:10am

Indeed, it is intended to be synchronized. A non-synchronized system yould be an interesting variation to bring up later, though.

Title: Re: Two-face Escapes Again
Post by rmsgrey on Sep 13^th, 2006, 5:13am

on 09/12/06 at 05:56:07, towr wrote:

You also need the crooks to start moving again if another crook catches up to them after they've stopped if you want to mimic synchronisation.

Title: Re: Two-face Escapes Again
Post by rmsgrey on Sep 13^th, 2006, 5:18am

A couple of observations that may or may not have any bearing on a solution:

1) [hide]Batman's strategy for choosing a route is irrelevant - the situation is symmetric enough that his chances are the same always going left as taking any other route[/hide]

2) [hide]Any given path has at most one crook on it, and some may have none.[/hide]

Title: Re: Two-face Escapes Again
Post by Whiskey Tango Foxtrot on Nov 2^nd, 2006, 9:00am

As the original riddle posted by the Wu-master himself has been dredged from the murky pit of riddles, I will submit a variation on the problem.

Suppose the gangsters are sent into the maze one by one. That is, each will enter the node tree by himself, but may still run into other stopped gangsters along the way, requiring a coin flip each time there is more than one at a node. For example, the first gangster will run to the first node and stop, since he is by himself and no coin flip is required. Then the second gangster will enter the node tree. When he reaches the first node, there will be two gangsters there, requiring a coin flip.

Note that all gangsters' first move is into the first node, not out of it.

Title: Re: Two-face Escapes Again
Post by rmsgrey on Nov 3^rd, 2006, 6:21am

on 11/02/06 at 09:00:14, Whiskey Tango Foxtrot wrote:

In this variation, what happens to the first gangster when the second gangster catches up?

Title: Re: Two-face Escapes Again
Post by Whiskey Tango Foxtrot on Nov 3^rd, 2006, 9:12am

Good question. I thought about stating this right off the bat and it turns out I should have.

The second gangster will reach the first node and be standing next to the first gangster. They will then both flip a coin and go their respective directions.

The third gangster will enter the first node and stop. Then the fourth gangster will meet the third at the first node and each will flip coins again.

Should the third or fourth end up on a node with any other gangsters, they will all flip again.

Title: Re: Two-face Escapes Again
Post by Three Hands on Nov 4^th, 2006, 3:28am

In other words, if there are ever at least 2 gangsters at a node, all gangsters at that node flip coins and move on, rather than any stopped gangsters staying at the node.

OK, g=Gangster, N=Node, number nodes from left to right and from near to far (so N1 leads to N2 and N3, N2 leads to N4 and N5, N4 leads to N8 and N9, etc.)

The 1 gangster case is trivial - goes to N1, stops, gets caught, Two-Face curses his lack of gang-members as Batman turns him in to the authorities, no coin-flips, total distance = 1 tunnel (the trip to node 1)

The 3 gangster case outcome is easy: Batman catches g3 at N1, since g1 and g2 have run off into the system before g3 gets there. Hence, most answers are similar to the 2 gangster case, but Batman automatically has a 1/3 chance of ending up where Two-Face is (assuming Batman stops after catching the first gangster. Otherwise he has a higher probability of finding Two-Face.)

For 2 gangsters:
g1 => N1 and stop
g2 => N1, g1 and g2 flip, 2 equally likely types of outcome - g1 and g2 go to the same node, or g1 and g2 go to different nodes. If different, they stop at N2 and N3, and one of them is caught by Batman at some later point guaranteed. If same, then they move to the same node (say N2) and then repeat the process with the same possible and equally likely outcomes, and with Batman then having a 0.5 chance of guessing the correct direction for finding a gangster.

So the gangsters have a 1-(1/2^n-1) chance of all escaping, where n is the number of nodes each travel to before they stop. Batman has a 1/2ⁿ chance of catching Two-Face.

The average number of coin-flips is approximately 4 (2 flipped at N1, (0.5[the chance of more coin-flips being required]*2[number of coins flipped]=)1 at N2 or N3, 0.5 at the next junction, 0.25 at the next, and so on) The average distance into the tunnels travelled is 3 tunnels (same reasoning, but add 1 for the journey to N1) and this is the average longest path taken.

The problem starts getting trickier (and more interesting) once the 4th gangster shows up, so I'll leave that for someone else ::)

Title: Re: Two-face Escapes Again
Post by Earendil on Nov 6^th, 2006, 12:33pm

Looks like this process leads to huge avalanches

Title: Re: Two-face Escapes Again
Post by Whiskey Tango Foxtrot on Nov 6^th, 2006, 12:59pm

on 11/06/06 at 12:33:04, Earendil wrote:

Looks like this process leads to huge avalanches

In processes with many gangsters, yes, it does.

Title: Re: Two-face Escapes Again
Post by Three Hands on Nov 6^th, 2006, 11:48pm

This is why I'm leaving it to someone else to either continue the method with a computer (I'm not well enough versed in computer programming to do this) or come up with a short-cut mathematically (I'm not clever/dedicated enough to do this :P)

Just from briefly thinking about the 4-gangster model, I'm not too keen on the size of the probabilities which could occur...

However, at least with any odd number, the likely outcome will be similar to the even number just before it, with the difference that Batman automatically captures the last gangster to enter the system, with the probability 1/n of it being Two-Face, where n is the number of gangsters. This halves the workload, at least ::)

Title: Re: Two-face Escapes Again
Post by Shiladie on Nov 27^th, 2006, 11:54pm

i'm no probability wizz, but i came up with an interesting variation.

what if batman started y turns behind the gang, but moved z junctions for every 1 the thieves move, so it is possible to catch up before the thieves stop moving

Title: Re: Two-face Escapes Again
Post by Whiskey Tango Foxtrot on Dec 5^th, 2006, 7:39pm

You could come up with a probability for a situation where y and z are defined. Writing a generalized equation in terms of y and z would take extensive amounts of work.