This problem has generated quite a bit of attention. No consensus has been reached by my think tank at the Pickover Discussion Group.
|You and an alien are playing a game that involves a set of tunnels. The top of the map is North. In the game, you start at the entrance to the tunnels located at the top of this diagram. As you travel, you may only travel south, east, and west, but never North. Given these permitted directions, each time you have a choice of tunnels, you are equally likely to choose either route. You win a neural stimulator that gives you ecstatic pleasure if you emerge at the tunnel marked "Win." What is the likelihood that you will win the prize?|
1) A B C Y 2) A B C F X 3) A B D E F XNotice that if you make the wrong turn for points D or E, you have already lost. Also note that A B C F E fails because eventually you will be forced to go south on D or E (remember, no backtracking).
A = (1/2)*B + (1/2)*Q B = (1/3)*Q + (1/3)*C + (1/3)*D C = (1/3)*B + (1/3)*F + (1/3)*R D = (1/2)*E E = (1/3)*D + (1/3)*F F = (1/2)*E + (1/2) P = (1/2)*Q Q = (1/3)*P + (1/3)*B R = (1/2)*C + (1/2)The odds of winning will be whatever the value of A turns out to be since this is where the maze runner gets to make his/her first choice. Fortunately life is very easy in that we can solve this system linearly. I took the "cheap" way out and plugged the matrix into my 49G. Assuming that I did not enter a number incorrectly or create a bad equation (and I did double check), A=161/880 or 18.3% Compared to the nearly 22.9% from problem 1, in this case it appears that going backwards would be a bad idea.
> > > | > ---'-------,---------,--a---, > | | | > | | | > | | | > |--,--b---| | > | | | > | c | > | | | > | |------| > | | | > | | | > | .---d--| > | | > | > 1/8 of the time you'll go through (a) and win. 1/16 of the time you'll go through (c) and win (not going through b) 1/16 of the time you'll go through (b) and win. If you get to (d) going West you're screwed, unless you backtrack.Andy replies, "I got the same result of 1/4 but I don't think it matters whether you can backtrack or not." Andy4996
> -----Original Message----- > From: Steve Brazzell [mailto:email@example.com] > Sent: Thursday, January 24, 2002 8:52 AM > To: CliffordPickover@yahoogroups.com > > [Cliff says, "By the way, when I devised the problem, I was > thinking that you wouldn't even try the paths that eventually > lead North -- if that matters. You would > only randomly choose between 'viable' paths. > If you only choose between > 'viable' paths, is my logic good?"'I don't think so, but perhaps I'm misunderstanding it. As I read your logic, the following (insultingly:) simple example has 4 total paths through it, 1 leading to a win, thus 1/4 chance of winning. But in this case isn't the only thing that matters whether you go East or West at the first junction (thus win=1/2)?
Tunnel 1 (left): 1 way of getting there Tunnel 2: 2 ways of getting there TUnnel 3: 0 ways Tunnel 4: 1 wayThus, the odds of winning are 1/4. Think of dropping a marble and trying to guess where it comes out. (We'd have to redraw this slightly so that gravity is pulling everything down properly, but you get the idea.)]
--- Steve Brazzell
wrote: > Cliff, > > What bugs me about your logic are the superfluous > paths that seem to affect the outcome. Consider > the modified maze I've put here > > http://www.innovatum.com/maze.gif > > I added a detour to the leftmost leg, which > increases by 1 the total number of paths and the > number leading to the leftmost path. Would this > change the likelihood of winning? By your logic it > would change it to 6/16, slightly decreasing your > odds. Somehow this doesn't seem right. What am I > missing?
I am inclined to agree with Steve on this one.
>> One way to solve this tunnel puzzle is to mark the >> number of possible routes you can take at each >> junction and add these numbers as you proceed to >> the four possible exits. For example, we can see >> there is only one way to get to the leftmost exit. >> The more ways she can get to an exit, the more >> likely it is that you will arrive there. The total >> number of possible routes to the exits is 1 >> (left-most tunnel) + 4 (left-middle tunnel) >> + 4 (right-middle tunnel) + 6 (right-most tunnel)= >> 15. Thus, the probability of you exiting at the >> right most exist is 6/15. This means the chance >> of winning the prize is about 40%.
--- Steve Brazzell
wrote: > Cliff, > > I'd say 1/4 of the time you will win (minus the time > you get stuck if you go West just before winning, > assuming you cannot backtrack).
-----Original Message----- > From: Steve Brazzell [mailto:firstname.lastname@example.org] > Sent: Thursday, January 24, 2002 2:48 PM > To: CliffordPickover@yahoogroups.com > Subject: RE: [CliffordPickover] Tunnels of Callicrates > > > I put a very quick-and-dirty one up here (windows-32 executable). > In it, I > place a bunch of turnstyles to show where you have travelled. > > http://www.innovatum.com/carrotstop/maze.exe > > [Cliff says, > Steve, before we execute the program, > can you explain to us what this does > and what did you learned as a result of running it?]Sure. Basically, I placed gates at key points throughout the maze (note, not at junctions, but just before). Some of them send you to a junction while others just send you on through (no choices left, leaving the maze). I made each gate keep a counter of every time it was passed through and each gate calls a random function that returns 0 or 1 to determine which way the person will go at the next intersection. The gate then passes control to the appopriate next gate.
> Steve, you mentioned bugs in your program. What's the latest > statistics for each tunnel of the puzzle? The bug was that the tunnel leading from leg 3 West to leg 2 was not being considered in one of the paths. With this fixed, a run of 150,000 marbles yielded: Tunnel 1: 12.61% Tunnel 2: 45.17% Tunnel 3: 17.17% Tunnel 4: 25.06%
From: "Steve Brazzell"for a layperson?....ok. Iss like Paw always say, heed say "boy, listen up! you see a fawk in the road, you take it." Well haff dem marbles you drop gone go right and about a half dozen othern gone go leff. Why'f att aint enuff, of the ones gone leff, half'o'dem gone drop on down dat secon shoot and the ones what don't, heck, they still got about half a chance a'fallin back t'ole number 2 'fo they get out. So number two gone get da line's share right off, even bleedin off some a'da ones what go right and drop down shoot 3. Now lookin at shoot 3 and 4, just eyeballin it says dey gone get filled up bout da same, so right after you done dropped 100 marbles you oughta see 50 of em goin right (50's bout half a 100). Half a dem gone end up in dat winnin shoot and d'utta half in shoot 3, 'cep like I done said 3's gettin bled off bout half the time towards ole 2.
[Cliff says, Amazing. So if you were a betting man, you'd pick tunnel 2. Can you explain exactly why we see these probabilities in a way that a layperson can understand? Do you see something interesting or counterintuitive in this little experiment?]
W=loss, 50% chance EEE=win, 12.5% chances ESS=loss, 12.5% chance EESS=win, 6.25% chance EESW=loss, 6.25% chance ESEE=win, 6.25% chance ESES=loss, 6.25% chance.Adding these up, there is a 75% chance of losing, and a 25% chance of winning
* * A*B * * * * * C*D * * Suppose you are travelling west, and reach C. Which of the following is the case? a) You are allowed to go north to B. The prohibition on going north only applies when you have a choice of direction. b) You can't go north to B, so you must turn around and go east to D. c) You can't go anywhere, you don't emerge anywhere, and you lose.Is there a 100% likelihood that you start out moving south?
1840 wins in 10000 trials or 18.40% with back-tracking not allowed 2282 wins in 10000 trials or 22.82%
1) Left, straight, straight (all options after this win) = 1/8 2) Left, straight, right, straight (ditto) = 1/16 3) Left, right, left, straight (ditto) = 1/16 All other directions fail. The answer is 1/4 or 25%The only other difference is if you intended "turn around" as a valid tunnel to follow at an intersection. I assumed not.
ProbTotal = 0 For each UniquePathToWin ProbGate = 1 For each gate in path ProbGate = ProbGate * 1/(NumChoicesAtGate) endFor ProbTotal = ProbTotal + ProbGate endFor
For Problem 1 p(4)=p(win)=3/16 and all probabilities are as follows: p (1)=1/16 p(2)=7/32 p(3)=13/32 p(4)=3/16 p(5)=1/8. For Problem 2 p(3)=p(win)=1/16 and all the probabilities are: p(1) =1/4 p(2)=11/16 and p(3)=1/16It easy to verify that the sum of all the probabilities for each case is 1, which means that the marble must fall somewhere. Kris
S:W (lose) S:E:E:E (win) S:E:E:S:S (win) S:E:E:S:W (lose) S:E:S:S (lose) S:E:S:E:S (lose) S:E:S:E:E (win)Mark Ganson: I stand corrected. The probability of winning is 25%. Thanks for helping me understand this tricky puzzle.
C1:W -> (lose) C1:E -> C2:E ->C3:E (win) C1:E -> C2:E ->C3:S ->C6:S (win) C1:E -> C2:E ->C3:S ->C6:W (lose) C1:E -> C2:S ->C4:S (lose) C1:E -> C2:S ->C4:E -> C5:S (lose) C1:E -> C2:S ->C4:E -> C5:E (win)(wrong) odds of winning: 3:7 (42.86%) (wrong)
Start | | | | ________________________| |___________________________ | _______ ____________C1___C2 _________C3 _______ | | | | | | | | | | | | | | | | | | | | | | |____ | | | |_________| | | | | __ | | | |C4___C5 ___C6| | | | | | |__| | _________| | | | | | | | | | |____ | | _______ | | | | | | | | | | | | | | | | | | |_______| | | | | |_______| | | | | | | _______ | | | | _________| | | | | | | | | | | | | | |___| | | | | | | | | | | _____| | |_______| | | | | | | | |_________ | | | | | | | | | lose lose lose win You have 6 choice points, which I have labeled C1, C2, C3, C4, C5, and C6. Here are the ways to win: 1) C1:East ->C2:East -> C3:East 1/2*1/2*1/2 == 1/8 2) C1:East ->C2:East -> C3:South ->C6:South 1/2*1/2*1/2*1/2 == 1/16 3) C1:East ->C2:South ->C4:East ->C5:East 1/2*1/2*1/2*1/2 == 1/16Thus, 1/8 + 1/16 + 1/16 == 1/4 probability of winning.
email@example.com (Mark Ganson):
Tunnels of Callicrates
(The following assumes we cannot double back on ourselves. For example, if we are headed East and come to a point where we may choose to continue East or to go South, we may not choose to turn around and go West.)
Though there are many choices to be made in navigating the maze, we really only need to be concerned with 6 choices, which I have labeled C1 - C6.
Coming down the maze South from the Start, we find our first choice, which we will label C1. C1 offers 2 options, East or West. If we go West, we always lose. If we go East, we will win some and we will lose some. Going East from C1, we come to C2, where our options are South or East. Whether we go South or East, we can still win or lose. Continuing East from C2, we come to C3, where we can go East or South. East at C3 guarantees a win. If we go South at C3, we might win or we might lose. Going South from C3, we come to C6 where we can go South, which always wins, or West, which always loses. Let's go back to C2 and head South from there. The next choice we come to is C4 where we can go South or East. South always loses, East wins some and loses some. Let's go East where we find C5. At C5 South always loses and East always wins.
(Thanks to Bob Morris for his ASCI drawing, which I have modified here.)
Start | | | | ________________________| |___________________________ | _______ ____________C1___C2 _________C3 _______ | | | | | | | | | | | | | | | | | | | | | | |____ | | | |_________| | | | | __ | | | |C4___C5 ___C6| | | | | | |__| | _________| | | | | | | | | | |____ | | _______ | | | | | | | | | | | | | | | | | | |_______| | | | | |_______| | | | | | | _______ | | | | _________| | | | | | | | | | | | | | |___| | | | | | | | | | | _____| | |_______| | | | | | | | |_________ | | | | | | | | | lose lose lose winOnce you commit to going East from C1, you have a 50% chance of winning. Once you commit to going East from C2, you have a 66.67% chance of winning. If you go South from C2, bringing you to C4, you then have a 33.3% chance of winning. If you get to C6 from C3, your chances are 50% of winning. If you get to C6 from C5, you are assured of winning. So, the most critical choices, resulting in winning or losing are at C1, C3, C4, C5, and C6. Some of the choices are only decisive if you make the right/wrong decision, such as C1, C3, and C4. These three choices only produce one endgame result each (win or loss result). Two of the choices are the most critical of all. These are C5 and C6, which can result in both wins and losses. So, with these 2 choices, you have 4 potential decisive results. To recap: C1, C3 and C4 produce one decisive result each. C5 and C6 produce two decisive results each. This gives us a total of 7 decisive results, which means they produce a total of 7 win/loss results. Of these 7 decisive results, 3 are wins and 4 are losses. The odds of winning are therefore 3:7 (42.86%) Here is a list of the potential paths that result in wins or losses:
C1:W -> (lose) C1:E -> C2:E ->C3:E (win) C1:E -> C2:E ->C3:S ->C6:S (win) C1:E -> C2:E ->C3:S ->C6:W (lose) C1:E -> C2:S ->C4:S (lose) C1:E -> C2:S ->C4:E -> C5:S (lose) C1:E -> C2:S ->C4:E -> C5:E (win)odds of winning: 3:7 (42.86%)
firstname.lastname@example.org (mensanator)responds to the previoius analysis: That's not correct. The seven decisive results are NOT equally likely.
> > > Here is a list of the potential paths that result in wins or losses: > > C1:W -> (lose) The probability of this happening is 50%. > C1:E -> C2:E ->C3:E (win)So the sum of all C1:E paths must be 50% also. Since C2 will only be reached 50% of the time, the two choices are 25% W and 25% S. With C3 being reached only 25% of the time, the two choices are E 12.5% and S 12.5%. Thus, this winning path happens only 12.5% of the time.
> C1:E -> C2:E ->C3:S ->C6:S (win)
Each decision point cuts the probability in half. Since we arrive at C6 only 12.5% of the time, the critical choice (S) happens only 6.25% of the time.
> C1:E -> C2:E ->C3:S ->C6:W (lose) > C1:E -> C2:S ->C4:S (lose) > C1:E -> C2:S ->C4:E -> C5:S (lose) > C1:E -> C2:S ->C4:E -> C5:E (win)
C2:S is 25%. C4:E is half of that or 12.5%. And C5:E is half again or 6.25%
> > odds of winning: 3:7 (42.86%)
Summing the winning paths 12.5% + 6.25% + 6.25% = 25% >