wu :: forums « wu :: forums - Two-face Escapes Again » Welcome, Guest. Please Login or Register. Jan 29th, 2022, 5:13am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: towr, SMQ, Grimbal, Eigenray, Icarus, ThudnBlunder, william wu)    Two-face Escapes Again « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Two-face Escapes Again  (Read 1685 times)
Whiskey Tango Foxtrot
Uberpuzzler

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

Gender:
Posts: 1667
 Two-face Escapes Again   « on: Sep 11th, 2006, 10:35am » Quote Modify

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 ...

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.
 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
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Two-face Escapes Again   « Reply #1 on: Sep 11th, 2006, 2:51pm » Quote Modify

A small hint for 4) 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.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Whiskey Tango Foxtrot
Uberpuzzler

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

Gender:
Posts: 1667
 Re: Two-face Escapes Again   « Reply #2 on: Sep 11th, 2006, 3:19pm » Quote Modify

Exactly, towr.  Good hint, but it took away some of the fun, as that is usually an interesting discussion.
 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
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863
 Re: Two-face Escapes Again   « Reply #3 on: Sep 11th, 2006, 3:26pm » Quote Modify

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?
 IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Whiskey Tango Foxtrot
Uberpuzzler

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

Gender:
Posts: 1667
 Re: Two-face Escapes Again   « Reply #4 on: Sep 11th, 2006, 4:04pm » Quote Modify

on Sep 11th, 2006, 3:26pm, 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.
 « Last Edit: Sep 11th, 2006, 4:24pm 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
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863
 Re: Two-face Escapes Again   « Reply #5 on: Sep 11th, 2006, 5:04pm » Quote Modify

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.
 IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Whiskey Tango Foxtrot
Uberpuzzler

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

Gender:
Posts: 1667
 Re: Two-face Escapes Again   « Reply #6 on: Sep 11th, 2006, 8:28pm » Quote Modify

Correctamundo.  Only 3 more to go.
 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
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7517
 Re: Two-face Escapes Again   « Reply #7 on: Sep 12th, 2006, 5:00am » Quote Modify

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?
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Two-face Escapes Again   « Reply #8 on: Sep 12th, 2006, 5:56am » Quote Modify

on Sep 12th, 2006, 5:00am, Grimbal wrote:
 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?
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.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Whiskey Tango Foxtrot
Uberpuzzler

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

Gender:
Posts: 1667
 Re: Two-face Escapes Again   « Reply #9 on: Sep 12th, 2006, 8:10am » Quote Modify

Indeed, it is intended to be synchronized.  A non-synchronized system yould be an interesting variation to bring up later, though.
 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
rmsgrey
Uberpuzzler

Gender:
Posts: 2846
 Re: Two-face Escapes Again   « Reply #10 on: Sep 13th, 2006, 5:13am » Quote Modify

on Sep 12th, 2006, 5:56am, towr 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.

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.
 IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2846
 Re: Two-face Escapes Again   « Reply #11 on: Sep 13th, 2006, 5:18am » Quote Modify

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

1) 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

2) Any given path has at most one crook on it, and some may have none.
 IP Logged
Whiskey Tango Foxtrot
Uberpuzzler

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

Gender:
Posts: 1667
 Re: Two-face Escapes Again   « Reply #12 on: Nov 2nd, 2006, 9:00am » Quote Modify

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.
 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
rmsgrey
Uberpuzzler

Gender:
Posts: 2846
 Re: Two-face Escapes Again   « Reply #13 on: Nov 3rd, 2006, 6:21am » Quote Modify

on Nov 2nd, 2006, 9:00am, Whiskey Tango Foxtrot wrote:
 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.

In this variation, what happens to the first gangster when the second gangster catches up?
 IP Logged
Whiskey Tango Foxtrot
Uberpuzzler

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

Gender:
Posts: 1667
 Re: Two-face Escapes Again   « Reply #14 on: Nov 3rd, 2006, 9:12am » Quote Modify

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.
 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
Three Hands
Uberpuzzler

Gender:
Posts: 715
 Re: Two-face Escapes Again   « Reply #15 on: Nov 4th, 2006, 3:28am » Quote Modify

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/2n-1) chance of all escaping, where n is the number of nodes each travel to before they stop. Batman has a 1/2n 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
 IP Logged
Earendil
Newbie

Gender:
Posts: 46
 Re: Two-face Escapes Again   « Reply #16 on: Nov 6th, 2006, 12:33pm » Quote Modify

Looks like this process leads to huge avalanches
 IP Logged
Whiskey Tango Foxtrot
Uberpuzzler

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

Gender:
Posts: 1667
 Re: Two-face Escapes Again   « Reply #17 on: Nov 6th, 2006, 12:59pm » Quote Modify

on Nov 6th, 2006, 12:33pm, Earendil wrote:
 Looks like this process leads to huge avalanches

In processes with many gangsters, yes, it does.
 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
Three Hands
Uberpuzzler

Gender:
Posts: 715
 Re: Two-face Escapes Again   « Reply #18 on: Nov 6th, 2006, 11:48pm » Quote Modify

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 )

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
 IP Logged
Newbie

Posts: 2
 Re: Two-face Escapes Again   « Reply #19 on: Nov 27th, 2006, 11:54pm » Quote Modify

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
 IP Logged
Whiskey Tango Foxtrot
Uberpuzzler

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

Gender:
Posts: 1667
 Re: Two-face Escapes Again   « Reply #20 on: Dec 5th, 2006, 7:39pm » Quote Modify

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.
 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 Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »