Tunnels of Callicrates, Solution Ideas

I welcome your feedback.

This problem has generated quite a bit of attention. No consensus has been reached by my think tank at the Pickover Discussion Group.

Tunnels of Callicrates

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?


For this problem I want you to pretend you are a "mindless marble" always falling down or right or left (but not up). The marble keeps going until it reaches one of the four exits. This is the problem I had in mind.... What is your solution?



Analysis 1



From: David Jones

To start the problem off, lets label each intersection (or choice) with a letter. The diagram shows points A-F, X, and Y. Second, to make things slightly easier, notice that when you get to either X or Y that you have won. You cannot lose from either of these points regardless of how you got there. Since we will be measuring probabilities, it is easier to measure them going to points X and Y rather than to the final destination. Points P, Q, and R are only used in the second problem.

Problem 1: What are the odds of winning assuming that I never backtrack. Another way to ask this is "How can I get to X or Y?" Here are the only possible ways of doing so:
1) A B C Y
2) A B C F X
3) A B D E F X
Notice 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).

From here, the probability is easy. Each point only offers one of two choices. The odds of taking path one are (1/2)^3, path two is (1/2)^4, and path three is (1/2)^5. The sum of these comes to 7/32 or 21.9%.

Problem 2: What are the odds of winning assuming that I can backtrack? Again I only care about getting to points X and Y, but if I can retrace my steps the are many more ways (infinite in fact) that I can still win and by the same token still lose. Thus, path modeling is not desireable. What we need to do is compute the odds of winning from each point along the path. For example:

Assume that I am on point R. What are my odds of winning? I have a 1/2 chance of choosing point X which is a guaranteed winner. But I also have a 1/2 chance of choosing point E. Thus the odds of winning are 1/2 + (1/2)*E. Assume I am on point E. There is a 1/3 change of going to D, F, or going south and losing. Thus I get E = (1/3)*D + (1/3)*F + (1/3)*0. We will have to repeat this idea for each point. Notice a few things however. First, point C now has three choices, not two. I can go to point B, F, or P, so not all points are governed by a 1/2 probability as in the previous problem. Second, we now need to add extra points P, Q, and R. When I get to P I have two choices, I can either go south or return to C. Same ideas for Q and R. Finally, notice that point A doesn't count as a junction except as an entry point. In other words, if I am on point Q, I would not go to east to point A, I would go east to B. Stopping at point A would be just like stopping midway between P and Q; there is no purpose to it.

Applying all of these rules to every point on the map yields the following set of equations.
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.

Incidently, if you remove points P and R under the premise that they are not junctions and that the traveller must continue down that hallway, A comes out 1/6 making things even worse. So even when you allow backtracking, the solution to problem depends on when you allow the runner to choose a direction.

Davy

Analysis 2

From: "andy4996"

I assume that your "valid choice" mean a choice where the outcomes are unknown. Based on this assumption, whenever I can see the "win" exit a valid choice will not exist anymore even though there might still be tunnels branched out other ways.

Three possible routes leading to the exit are: E-E-E, E-E-S-S, and E-S-E-E

Therefore, I think the chance to win is (0.5)^3+(0.5)^4+(0.5)^4 = 0.25 or 25%

Analyis 3

From: "Steve Brazzell"

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

Steve

> 
> 
>    |
> ---'-------,---------,--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

Comment

From: Craig Becker

Just some trivia: there's a Greg Egan short story (I think it's called "Into The Darkness" in his collection _Axiomatic_) that has a main premise very much like this puzzle: some kind of malfunctioning time machine appears randomly and creates a thick spherical "shell" around itself in which light and matter can only move _inwards_. When the time machine departs, everything in the shell disintegrates, so it behooves people to make their way to the center. Of course, since light can only move inwards, this means you're walking into a big black wall. And if you make a wrong turn, you're dead.

Craig

Analysis 4

From: "plasmagen"

We have so many different answers for this one. Here is my logic. Let me know if this logic applies, or if it only applies when the problem is worded in a particular fashion.

I can see this problem is a tough one since everyone has a different answer. I'm happy to accept different answers so long as we can agree on them given certain assumptions. (My intent is to put this in a book.)

My logic:

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. (That means it's not too likely you would arrive at this exit by randomly walking through the tunnels.) 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%.

Analysis 5

From: "Steve Brazzell"

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



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?

Steve

[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?"']

Analysis 6

From: "Steve Brazzell"


> -----Original Message-----
> From: Steve Brazzell [mailto:steve@brazzell.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)?



[ Cliff says, for your fascinating variation, I would say that
Tunnel 1 (left): 1 way of getting there
Tunnel 2: 2 ways of getting there
TUnnel 3: 0 ways
Tunnel 4: 1 way
Thus, 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.)]

Analysis 7

From: David Jones

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


My objection to this is that the solution assumes that each path is as equally likely as the other. Unfortunately this is not the case. A path that required three choices, regardless of the final destination, is still less likely to be traveled than a path that requires only two choices. You can solve the problem this way, but only if you apply a weight to each path where the weight indicates the probability of each path taken.

Incidently, a coworker of mine who has a degree in philosophy with a minor in math did the problem independently and also came up with the 7/32 answer that I did, so I feel more confident in that solution. Since there are differring answers, perhaps one of the programming people in the group can write a simulation for it as an external verification.

Davy

Analysis 8

From: David Jones

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


I have to retract my 7/32 answer. I agree with Steve on this. I hastily assumed in my solution that the path A B D E F X that it mattered what you did at F. Really, you don't get a choice since the only way is south.

Davy

Analysis 9 (Simulation)

 -----Original Message-----
> From: Steve Brazzell [mailto:steve@brazzell.com]
> 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.

You release a new traveler through the maze by pressing the GO button and may specify how many travelers to let though at a time. Some sample runs are as follows:

12600 travelers. Gates (left to right): 12.33%, 39.25%, 23.67%, 24.78% 32767 travelers. Gates (left to right): 12.70%, 38.9%, 23.23%, 25.17% 1M travelers. Gates (left to right): 12.42%, 39.07, 23.52%, 24.99%

For those who care about the programming (in 2 words: Quick and Dirty), the program has one recursive procedure "Go" which is passed which gate is being visited along with the direction being travelled. Within the procedure, a case statement selects the gate and each gate calls the Go routine again, passing one of its two child gates. The "leaving the maze" gates don't call Go again, thus the procedure can exit.

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


Steve

[Cliff says, Steve are you assuming what I assumed:

(For this problem I want you to pretend you are a "mindless marble" always falling down or right or left (but not up). The marble keeps going until it reaches one of the four exits.)]

Yes. In fact, I had a strong urge to call the button "Drop" and the traveler "marble" even before you said that. No "north" or "180 degree turns" are allowed. The only thing unlike a marble is that during a straight drop downward the marble can turn left or right...well, that and also that the marble can roll straight over a drop without falling...geez)

(Incidentally, the 2nd and 3rd legs should be more like 45/17, not 39/24--there was a bug in version 1.0a)
From:  "Steve Brazzell"  
[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?]
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.

Analysis 10



qurqirishd@aol.comHAHA (The Qurqirish Dragon)

I am going to assume that you never backtrack (i.e. if you are going East when you hit an intersection, you will NOT choose West.) I will abbreviate all compass directions from now on.

At the first point, you can go E or W. If you go W, you cannot get to the goal. After two choices, (ignoring determined results) we have either EE or ES. Neither one is a guaranteed win or loss, so we continue. After 3 choices (again, ignoring determined results), we have EEE, EES, ESE, and ESS. EEE guarantees a win. ESS guarantees a loss. After 4 choices, we finish determination of all routes. We have EESS, which is a win; EESW, which is a loss; ESEE, which is a win; and ESES, which is a loss. Listing the results, we have:
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

Analysis 11

"Ed Murphy"

Consider the parts of the diagram that look like this:
*   *
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?

Is there a 0% likelihood that you ever voluntarily come to a permanent stop before emerging?

When you reach an intersection, and you have two or three choices of direction, may you choose to reverse your previous direction (i.e. switch from east to west, or vice versa)?

Is there a 0% likelihood that you ever voluntarily change direction at a non-intersection before emerging?

Analysis 12

mensanator@aol.com (Mensanator)

I constructed a state machine in Excel and got the following results: with back-tracking allowed

1840 wins in 10000 trials or 18.40%

with back-tracking not allowed

2282 wins in 10000 trials or 22.82%

Analysis 13

"Michael Crowder"

Seems pretty simple to me. The only ambiguity lies in the framing of the puzzle. You don't say what happens if the mouse reaches a point at which he cannot move (i.e. the only option is north - which is against the rules). Does he turn around? I will assume he must.

Define all directions as seen by the mouse.

The sum of all possible correct routes is your answer.
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.

Two More Tunnel Problems

You are playing a game involving a maze of tunnels. In the game, you drop a marble at the entrance at the top of this diagram. Each time the marble has a choice of routes, it is equally likely to fall either way. The marble is falling, so it is never able to back up. You win the game if the marble comes out at the spot marked "Win"?

Problem 1

Problem 2
According to some people's false logic you, there is equal probability that the marble will get to the rightmost or leftmost exits. Doesn't it look funy to you? Yes, there are 6 different pasages, but don't forget that they don't have the same probability of occuring. The answer should be: on each junction the marble will go in the right direction with 50% probability. So, if we have four junctions, the answer is p=0.5*0.5*0.5*0.5=0.0625=6.25% and not 1/6 as you said. Thanks for your enjoyable site. It's delitious for Math-lovers. Jack Kuperman.


Steve Brazzell: If I'm looking at this right, in your second maze 1/2 of the marbles go left at the first junction. Of these, 1/2 fall out the first tunnel. So for the first tunnel, the odds are 1/2 of 1/2, or 1/4. Half of the marbles go right at the first junction. Of these, 1/2 go left at the next junction (leaving 1/4 of the marbles still going right). Of these, 1/2 fall out the next junction (leaving 1/8th). Of this 1/8th, 1/2 fall out at the last junction, leaving 1/16 winning.

Hi Steve (Brazzell), I think I'm latching on to your (valid) method. One way to solve this class of tunnel problems is to first draw all paths that get you to a "sure win" tunnel. At each intersection, you place a "1/2" representing a binary decision. For each path, you multiply the 1/2s along the route. And then, in the end, you sum the products for each path. Thanks for all the feedback, Cliff
Steve Brazzell says: Exactly. I think the general algorithm would be something like this, which would account for junctions (gates) with more than 2 choices:

ProbTotal = 0
For each UniquePathToWin
ProbGate = 1
For each gate in path
ProbGate = ProbGate * 1/(NumChoicesAtGate)
endFor
ProbTotal = ProbTotal + ProbGate
endFor


Kris Musial : The two problems below are significantly simpler than the two tunnel problems posted earlier, because they don't involve loops. In the earlier problems we could move east-west infinitely, which made them harder to solve especially in the case of Tunnels of Callicrates.
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/16
It easy to verify that the sum of all the probabilities for each case is 1, which means that the marble must fall somewhere. Kris


Mark Ganson: Hello Cliff,

I came across your website and thought I would tackle the Tunnel of Callicrates puzzle. I calculate the odds of winning to be 3:7 for a probability of roughly 42.86%. This assumes that the marble can never turn back on itself and go the other direction. For example, coming down from the Start position, we can go East or West. If we go West, we always lose unless when we get to the next tunnel where we can go West or South, we turn around and go back East. If you can turn back on yourself and do a 180 degree change of direction, you might get stuck in an infinite loop, bouncing East to West to East to West... and never win or lose. If i = infinity, I'd say the chances of getting caught in the infinite loop would be 1/(i-1) or thereabouts.

Here is an enumeration of the potential decisions that result in wins or losses (beginning from Start point) assuming you cannot make any 180 degree changes of direction:
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.

I wrote a bit of Java code to verify that the odds of winning are 25%. I ran the simulation out to 100000 iterations, making 50% random direction decisions at each choice point. Each time it came back very close to 25% wins and 75% losses. If anybody want to see my java source, send me an e-mail with Tunnels.java in the subject line.

I think the problem with my original (incorrect) answer was that I was equating the different paths with having equal likelihoods of happening.

To recap:
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)

The problem with the above is that I was considering a loss at C1 to be the equivalent of a loss at C6. This was a mistake since getting a loss at C1 is much more likely to happen than getting a loss at C6 for the simple reason that every trip through the tunnel passes through C1 while only a fraction of them will go through C6. We can win or lose at the following choice points:

C1, C3, C6, C4, and C5.

We can refer to C1 as a 1st step choice point, C3 and C4 as 3rd step choice points, and C5 and C6 as 4th step choice points. The 4 4th step choice points present 2 ways to win and 2 ways to lose, so they cancel each other out. The 2 3rd step choice points present 1 way to lose and 1 way to win, so they cancel each other out. The lone 1st step choice point (C3) presents only 1 way to lose and no way to win directly, so it should have been given a greater weighting in my original analysis. As I had correctly stated in my original post, once you make the decision to go east from C1, you have a 50% probability of winning. So, we can simply by looking at the puzzle as having 1 key choice point, C1, where choosing west gets a loss and choosing east gets a 50/50 chance of winning.

C1:W -> lose C1:E -> 50/50 chance to win or lose

So, 50% of the time you will be in position to win 50% of the time. 50% of 50% = 25%. 50% of the time plus 50% of 50% of the time, you will lose. 50% + 50% of 50% = 75%. In the end, the probability of winning is 25%.

I repeat: the probability of winning is 1/4. Consider the following ASCII TEXT drawing:

                        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/16
Thus, 1/8 + 1/16 + 1/16 == 1/4 probability of winning.

From: "kmusial_2000"

Mark provided an interesting twist on the Tunnels of Callicrates puzzle: "the marble can never turn back on itself and go the other direction". This version simplifies the original one because it eliminates loops from the marble movement.

The possible paths listed (inserted below) are valid, however, I think that the suggested probability of winning equal to 3/7 is wrong. It would be right if each of the paths is equally probable (3 successes out of 7 possibilities). But the paths are not equally probable and the longer the path the less likely it is: to be precise the probability is equal to 1/2 to the power of the number of decision points. For example the probability of the first path is 1/2, second - 1/8, third - 1/16, etc. If we count this way the probability of winning is 1/4. I confirmed this with the simulation, in which the marble was thrown 1 million times and it landed at each of the four gates with the ratios: 0.13, 0.45, 0.17 and 0.25 (win).

By the way: the simulation which allows the marble to move back (original puzzle) gave the following ratios: 0.13, 0.48, 0.19, 0.19.

Regards, Kris

mwganson@hotmail.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                  win


Once 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%)

mensanator@aol.com (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% >


Derek Tunnel Enigma (Tunnels of Recursia)

From: Derek I'm somewhat worried that the moderator will be offended if members start posting their own versions of his puzzles, but what the hay... Here's another maze puzzle similar to the Tunnels of Callicrates. The main differences are:
- you can go any direction, north, east, south, west.
- There are two one-way doors, indicated by dotted
lines. The arrow indicates the direction of the door.
The story is slightly different too. In this case, the evil puzzlemeister, Clickover, has been feeding you tequila shooters all evening. Then, he dropped you at the start gate of the tunnel. Since it is completely dark, and you are mentally obliterated by this point, you are only capable of making random turns whenever you encounter a fork in the tunnel.

Like before, the problem is to find the probability that you will eventually crawl out of the "WIN" opening.

I think this one should be called "The Tunnels of Recursia".

PS, I don't know what the answer is.

Derek.

[Cliff says, sure, it's great to post your own puzzles. I'll assume it's OK for me to report on them, with proper credit to people, in my own books and website -- unless you tell me otherwise.] Solution "kmusial_2000"
I think the probability that I will "eventually crawl out of the WIN opening" is 2/3. I arrived at this number by some reasoning and a little calculation. I confirmed the result by a simulation in which I went into the tunnel (mentally obliterated) one million times and the ratio of times I showed up at the WIN gate was 0.6669. Regards, Kris


Derek Ross says: I got the same answer, but reversed... the probability of reaching the WIN gate was 1/2, and 2/3 for the LOSE gate.

I think that the probability is equal to the infinite sum:

P(win) = 1/2^2 + 1/2^4 + 1/2^6 + 1/2^8 ...

I didn't know how to calculate it formally, but the equation seemed to be converging to 0.33333...

Derek.

kmusial_2000"

Sorry, I swapped the LOSE and WIN labels on the gates (in both: my theoretical solution and simulation) and the answer is indeed reversed.

It's true that the probability is equal to the sum of the infinite series and since the series is geometric there is a simple formula to calculate it.
Thus: P(WIN) = 1/2*1/2*SUM(1/2*1/2)^i for i=0,1,...
P(WIN) = 1/4*1/(1-1/4)=1/4*4/3=1/3

Similarly P(LOSE) = 1/2*SUM(1/2*1/2)^i for i=0,1,...
P(LOSE) = 1/2*1/(1-1/4)=1/2*4/3=2/3
The extra term 1/2 in P(WIN) results from the necessity of moving to the east side where the WIN gate is.

Derek, in your last post you suggested 1/2 and 2/3 for the WIN and LOSE gates, respectively but it's simple type isn't it?

Kris

> Derek, in your last post you suggested 1/2 and 2/3 for the WIN and > > LOSE gates, respectively but it's simple type isn't it? Derek: Whatever the typo is, I agree with your answer of P(win) = 1/3 and P(lose) = 2/3.

Chuck says: From where you start you have a 50% chance of losing immediately, a 25% chance of winning immediately, and a 25% chance of starting over. We can ignore the case where you start over since it has no effect on whether you eventually win or lose so I'd say you have a 1/3 chance of winning and a 2/3 chance of losing.


Nick Hobson say:



Cliff, By a strict interpretation of the rules (no north and no backtracking) there are 8 possible outcomes: 4 tunnel ends, and 4 dead ends (in the transverse sections.) If backtracking IS allowed, the problem becomes more interesting and challenging.

Here is my solution. I express it in terms of the directions taken by the marble. A choice is separated by a comma.

The 6 possible winning routes are:
E,E,ES,S,S
E,E,ES,WSES
E,E,S,S,SES
E,E,S,S,ES,S
E,S,E,ES,SES
E,S,E,ES,ES,S
Each choice has p=1/2, giving a sum of 3/16. Yet another answer!

Actually, this is equivalent to Steve Brazzell's Analysis 3: 1/4 minus the probability of getting stuck by going West just before winning. I've called this possibility deadend 4, below, and its probability is 1/16.

Partly to satisfy myself that this logic is correct, and partly out of curiosity, I calculated the probabilities of the other possible outcomes. They sum to 1, which is encouraging!
Tunnel 1
========
W,WS,S
p=1/8

Tunnel 2
========
W,S,S,S
W,WS,ESES,S
E,S,S,WSWS
E,E,S,W,WS,WSWS
p=13/64

Tunnel 3
========
E,S,S,S,S
E,S,E,SWS
E,E,S,W,WS,S,S
E,E,S,W,WSW
p=17/128

Tunnel 4
========
p=3/16

Thus the probability of emerging from a tunnel is 83/128.

Deadend 1 (between tunnels 1 and 2)
=========
W,S,W
p=1/8

Deadend 2 (between tunnels 2 and 3)
=========
W,S,S,E
W,WS,ESES,E
p=1/8

Deadend 3 (between tunnels 3 and 4, left)
=========
E,S,S,S,E
E,E,S,W,WS,S,E
p=5/128

Deadend 4 (between tunnels 3 and 4, right)
=========
E,E,ES,S,W
E,E,S,S,ES,W
E,S,E,ES,ES,W
p=1/16

The probability of getting stuck in a deadend is 45/128.

So the possible outcomes, in descending order of probability,
are:

T2:       26/128
T4 (win): 24/128
T3:       17/128
T1,D1,D2: 16/128
D4:        8/128
D3:        5/128

Nick Hobson


Todd Redden says:

This solution involves plotting positions in the path beyond which the end result is predetermined. If you get to any of these colored squares, the end result is known, and no further inspection is necessary. All you have to do is look at the percentage of remaining chances which can lead to a given result at each turn.

You lose 50% of the time at A by turning right. Of the 25% that you go straight at B, you win 12.5% by going straight at C. Of the 25% that you turn right at B, you lose 12.5% by going straight at D. Of the 12.5% that you turn right at C, you win 6.25% by going straight at F, and lose 6.25% if you turn right at F. Of the 12.5% that you turn left at D, you lose 6.25% by turning right at E, and you win 6.25% by turning right at F.

Adding things up, you win 25% of the time.
- Todd Redden tmredden@snet.net


From Dominic : It's much easier to understand if you simplify the maze. On this modified map, I've marked places where a choice must be made with a yellow circle, grayed out areas that have no effect on the solution, and marked routes that guarantee failure in red. Looking at this map, there are 6 places where a choice must be made. 2^6 = 64, so let's start by dropping 64 marbles down the "tube" and assume that half will go down each path at an intersection. We'll count how many make it to the end. The green squares mark the number of marbles that have made it to that point in the tube. Only 16 of the 64 will reach the finish line, therefore the answer is 25%. Similar to Todd's answer, but easier to follow. -- Dominic Eldridge


From "David" :
Hi Cliff. Enjoyed the website, nice and challenging. The Tunnel, hmmm, seems everyone who has posted comments have analysed the heck out of it. Me, well by using a pencil to point to the tunnels on my screen and following the rules which says choices are move left, right or down and only these variants are allowed to either leave at the Win exit (or if you leave at the other exits and no neural stimulus - damn), the answer seems to be 5 routes will produce a win, and 4 will not - ergo 55.55% chance of winning. kind regards, David


From James Reimer :

I get a probaility of a win at 25% based on the assumption that at each intersection there are only two possibilities. Any time all the possibilities along a branch result in failure, that branch is eliminated. We are left with the sum of the probabilities of all the winning branches. See the analysis below. At each intersection, choices are designated by a direction (Left, Right or Down) and a probability, each time half of the previous probability.
L-50% >       >         >         > Failure
R-50% > D-25% > R-12.5% > D-6.25% > Failure  
                        > R-6.25% > Win
              > D-12.5% >         > Failure
      > R-25% > D-12.5% > L-6.25% > Failure
                        > D-6.25% > Win
              > R-12.5% >         > Win
The probabilities are added in the three winning branches which amount to .0625 + .0625 +.125 = .25 or 25%


From Hans Mikelson:

Hi Clifford,

I get the same answer as those who are getting 25% chance of winning. Attached is a diagram which hopefully explains my solution.

Bye, Hans Mikelson

P.S. I've been a big fan of your books for many years!


From Larry Kubicz:

Cliff,

Here's my analysis of the tunnel puzzle. I took a hands-on approach, which I figured would get to the heart of the matter. I went under the assumption that backtracking wasn't allowed.

For this, I borrowed the diagram supplied and labeled by David Jones. I just added another label, Z, at the intersection just north of Win. If you draw this out, it helps to draw little arrows to track the numbers going hither and yon through the tunnels.

I assembled 64 of my closest imaginary friends at the Start point. At each branch, half of those entering will take one fork, and half the other, which is why I chose a power of 2.

At A, 32 of our brethren will head west, never to be seen again. The rest head east.

At B, the remaining 32 will split: 16 heading east for C, and 16 heading south for D.

At C, the 16 will split: 8 heading east for Y, and 8 heading south for F.

At D, the 16 will split: 8 heading east for E, and 8 heading south for oblivion.

At E, the 8 from D will split: 4 continuing east for F, and 4 heading south for oblivion.

At F, th 8 from C will split: 4 continuing south for X, and 4 heading west for oblivion. The 4 from E will join up with the 4 from C, making a total of 8 heading south for X.

At X, the 8 from F will split: 4 continuing south to Z, and 4 heading west for Y.

At Y, the 8 from C will split: 4 continuing south to Z, and 4 heading west for X. This latter 4 will join up with the 4 from F, making a total of 8 proceeding south to Z.

At Z, we'll have 8 from Y joining 8 from X, for a total of 16, which yields the usual 16/64=25%.

BUT, perversely, half of those from Y will decide to turn west into a dead end. This leaves 12 to head south to Win, where they can mourn their lost brethren. 12/64=18.75%.

Larry Kubicz


From "George Greenwade":

I agree with the answers of .25 for a probability of winning and offer a textual presentation of the logic, based on the figure provided by David Jones at the start of the solutions.

This is a probability question that begs the question of is it better to look at the probability of an event happening (p) or the probability of an event not happening (1-p), but the bottom line is that the sum of two exclusive events (win/lose) must equal 1.

At point A, each path (east or west) occurs with equal probability of .5. If the westward path is chosen, it is impossible to get to WIN as neither tunnel P nor Q connect to WIN in a fashion consistent with the constraints of no northward movement.

Therefore P(win EAST) = 0 and the total cumulative probability (cumP) of winning (cumP(win)) is reduced to 0.50 at best and cumulative probability of losing (cumP(lose)) is at least 0.50.

If the eastward path is chosen, tunnels B, C, and R are possible, but not equiprobable.

Given three southbound tunnels for the eastbound traveler, the probability of being included in tunnel B is .25, tunnel C decays to .125, and tunnel R accepts all remaining travelers and is .125.

The critical point on tunnel B is D, the only possible way to achieve WIN. With equiprobable changes in direction at D, .5 of the .25 (.125) will continue southward to not satisfy the WIN criteria. Therefore, .25 of the total originally eastbound travelers will fail to WIN (.25*.5) =.125 will exit due south of B and may be added to the westbound failures, providing cumP(loss)=.625

For the .125 who travel east at point D, one half (.0625) will go south at point E, return to tunnel B and fail to win, providing cumP(loss)=.6875. The remaining eastbound travelers will get to point F and must eventually get to WIN, providing cumP(win)=.0625

Those travelers who go southbound at point C (.125) face one critical point, F. Again, given an equiprobable movement at this point, half (.0625) will go west, ending their trip at the foot of tunnel Q or tunnel B, providing cumP(loss)=0.75 and cumP(win)=.125

For the .125 who travel east and end at point R, the probability of winning is 1 as there is a turn point at Y, although it is not a critical point as northbound travel is disallowed at the terminal X (they behave as if they were simply dropped straight down tunnel C, which ultimately returns to tunnel R.

Net result cumP(loss)=.75 and cumP(win)=.25

---------------------------------------------------------

An aside which I will explore more as time allows: Provided that A is a one way door (travelers may not exit the system via the entrance), backtracking is allowed (i.e., at a point such as P, eastbound travelers may simply take a 180 degree turn and travel west) and full movement is allowed (i.e., northward is permissible within the system), I hypothesize that this problem reduces to a decay formula which, at the limit, becomes a half-life formula based on the outcomes (the exits). Note that this does not alter the simple solution above as the movement becomes equiprobable at each stage with only one possible winner (1 winner out of 4 possibilities or 1/4 or 0.25).

George


From Robert G. Brown:

The choice is: work on your puzzles or grade finals. Hmmmm.

So, in Tunnels of Callicrates, there appear to be two distinct families of solutions. In one, the trajectories are self avoiding (that is, when one hits a junction, one is not allowed to retrace one's steps back up the tunnel from which one came). In that case the solution is fairly pedestrian, I think -- just counting the fraction that lose at each signficant junction (one where one branch definitely loses or definitely wins) and tracking marble or alien flux leads to 25% who reach win, unless I miscounted (which is always a possibility:-).

However, the fiendish problem arises if one imagines that the alien enters a spinning wheel at each junction what whirls, opening on any of the TWO OR THREE possible pathways that lead away from each junction. That is, if at each junction the alien has an equal probability of retracing their steps back the way they came (provided the route back is permitted), one starts getting truly horrible series expansions for the probability flux that wins or loses summing over significant junctions, stuff like 1/2\sum_{n=1}^\infty (1/6)^n ultimately added to the 1/2 flux to the right at the very first junction from the series of successive reflections between that first junction and the first junction on the left, which is ITSELF further modified by higher order "multiple scattering" contributions from reflections from the first junction on the RHS and so forth. Yuk.

I actually am a statistical mechanic and do Monte Carlo, and it seems like the best way to find a very good approximation to the solution in this case (if one isn't attached to doing immense amounts of mindless algebra, which I actually am but can't take THAT much time away from grading finals:-) is to create a simple hash of significant junctions in e.g. perl, populate the toplevel junction and create stochastic trajectories through to eventual certain win or loss (e.g. 100% of the traffic to the left at the first junction on the left can never win), and just plain count the number that make it to "win". At the moment I'm having a hard time finding an intuitive hat, but given the symmetry of the of the first two junctions two the right and left of the primary one and the EXTRA junction on the right, I would expect a small additional probability flux to the lossy side from the SECOND junction on the right hand set of pathways and so an ultimate probability of winning somewhat less than 1/4. Can't quite make up my mind about flux conservation at e.g. the central link along the box between the first two right hand downward pathways -- clearly reflections from flux down the first RH pathway will increase the net loss along this pathway (I think) but the loss will be ameleorated somewhat symmetrically by reflections from the flux down the second path at the first junction.

I assume that you probably know the algebraic answer to this one. If you care I'd be glad to share the results of my simulation, if I end up writing one.

BTW, you might edit the problem to make it clear whether your use of the word "either" in "equally likely to choose either route" is binary (self avoiding) or not (the more interesting problem above). The common usage is binary (either A or B, but not EITHER A or B or C) and English shouldn't be an obstacle to a nice little mathematical problem.

rgb

--
Robert G. Brown http://www.phy.duke.edu/~rgb/
Duke University Dept. of Physics, Box 90305
Durham, N.C. 27708-0305


From Ben Daglish:

Has anyone done this? - I couldn't see it on the page.... Seems the obvious thing to do. (Use a fixed font :) )
              * 
              * 
             100% 
              * 
************************************* 
*        *        *        *        * 
20%      20%      20%      20%      20% 
*        *        *        *        * 
*        *        *        *        * 
*        *        ***10%****        * 
*        *        *   *    *        * 
*10%*    *       15% 10%  15%       * 
*   *    *        *   *    *        * 
*   *    *        *   *    ********** 
*   ******   *7.5%*   *    *        * *        *   *    *   *   17.5%   17.5% 
10%      30%  *   7.5% *    *        * 
*        *   *    *   *    *        * 
*        *****    *****    ********** 
*        *        *        *        * 
*        *        *        *        * 
*        *        *        *        * 
10%     37.5%    17.5%    17.5%    17.5% 
Therefore it's a 17.5% probability, assuming backtracking / never taking possible North tracks. Cheers, Ben Daglish

Graham says:
In all your tunnel problems, your solvers would find life much simpler is they started out with 2^n (assuming binary gates and n big enough - usually n=5 is enough) marbles, and then counted how many go in which direction at each gate. I'm also interested in the faith placed in simulations - if you base the simulations on the assumptions you originally used then the simulation is always going to prove you were right. Logic always does that. Interesting page, though.

Gordon says: The marble drops, first choice, east or west. Each has 1\2 chance. West 1\2 is sure failure. Lets asume the east 1\2 is taken. Second choice south or continue east. Each has 1\2 of the remaining half or 1\2 chance. Lest expand on the south 1\4 first. Third choice south or east. Each has 1\2 of the remaining 1\4 chance. The south 1\8 is sure failure. Lets asume east is chosen. The fourth choice is to continue east or to turn south. Each has 1\2 chance of the remaining 1\8. The south choice is sure failure. The east choice is sure success. This gives 1\16 chance of winning if the second choice is south. Now if the second choice is east the third choice is to continue east or south. Each has 1\2 of the remaining 1\4 chance. If the south 1\8 is chosen the fourth choice is to continure south or to turn west. Each has 1\2 of the remaining 1\8 chance. The west 1\16 is sure failure where the south 1\16 is sure success. That being said there are two seperate ocassions where there is a 1\16 chance of success and one where there is a 1\8 chance. Therefore there is a 1\4 chance of success. Alternately 1\2 have no chance. Choice two 1\16 of that 1\4 that drops south win that leaves 3\16 that loose. Choice three 1\16 of the 1\8 that drop south win that leaves 1\16 losing. Do some addition of the losers 1\2 + 3\16 + 1\16 = 3\4. The only thing that could complicate things more is if you added in the possibility of reversing direction. If you want to see try that one e-mail me back. Not clear enough?


Bob Ewell says:
This analysis uses the diagram from the very first, which, except for a minor error that the author made, is the correct approach. Moreover, I have completely analyzed the paths through the tunnels (with no backtracking) to ensure that the sum of all paths’ probabilities is 1.0. We don’t need to consider all possible paths--we need only trace a path until its outcome is certain.

First path: go west at A, and you lose. You have a 1/2 probability of doing that. Nothing else on the west side of the start is material since there is no way to get back to the win tunnel from there.

Second path: ABD, going south at D. You lose. Probability is 1/8

Third path: ABDE, going south at E. You lose. Probability is 1/16

Fourth path: ABDE, going east at E. You win. Probability is 1/16

Fifth path: ABCF, going west at F. You lose. Probability is 1/16

Sixth path: ABCF, going south at F. You win. Probability is 1/16

Seventh path: ABCR: You win. Probability is 1/8

The sum of all probabilities = 1/2 + 2 x 1/8 + 4 x 1/16 = 1.0

Of those, the ones corresponding to a win are one at 1/8 and two at 1/16 = 1/4.

This solution is complete and correct. If there is no backtracking, there is no room for doubt or discussion. We have a complete sample space with the probabilities adding to 1.0.


Tunnels of Callicrates, the solution of
---------------------------------------
Written 2008-03-08 by Anders Hallström


Dear Cliff,

I find the Tunnels of Callicrates an interesting problem and I have prepared a solution for it.

We have seen that the solution depends heavily on how different people interpret the given conditions.

Reading your description and not peeking at other peoples's work, I naturally, without thinking much about it, made the most liberal interpretation of when there is a "choice". I assumed a corner is to be seen as a junction where the marble can bounce. I also assumed that the initial junction (node A below) continues to be seen as a junction although we can never go up again. This, I believe, gives the hardest and most challenging problem.

Although I prepared this solution independently before looking at other people's work, I will now, for everybody's convenience, reuse the labelings that David Jones used in his analysis. (Adding G,H,I,J) (Note that the uninteresting parts of the maze have been pruned off!)

               |
               |
   P --- Q --- A --- B ------- C --- R
   |     |           |         |     |
   |     |           |         |     |
   |     |           D -- E -- F     |
   |     |           |    |    |     |
   |     |           |    |    |     |
   I     J           G    H    X     Y
  
  (LOSE) (LOSE) (LOSE)(LOSE)  (WIN)  (WIN)
Solution to worst-case interpretation (I1):
------------------------------------------
Note that we now have a game that involves potentially infinite bouncing. However, the probability of getting stuck on a level for a long time is very low. The probability of never falling down is zero. The ride could however go on for an unlimited (but finite) time.

Consider pA = a sort of generalised probability of reaching node A, *including* all possible repetitions. Such a generalised probability can be larger than 1. Indeed, we start at node A with probability 1 and we may revisit later, so pA > 1. Instead of attempting to compute sums of infinite series, we are going to solve for these node probabilities indirectly.

Transition probabilities: pAQ = 1/2 = pAB, pQA = 1/3 = pQJ = pQP, pPQ = 1/2 = pPI, etc. pIP = pJQ = pGD = pHE = pXF = pYR = pDB = pFC = 0

Net probability flow from A to Q: pAQtot = pA*pAQ - pQ*pQA = pA/2 - pQ/3

This represents the probability of ever leaving node A towards node Q and not returning.

From Q to P:
pQPtot = pQ*pQP - pP*pPQ = pQ/3 - pP/2

From P to I:
pPItot = pP*pPI - pI*pIP = pP/2 - 0

By flow conservation, net flow from Q to P must equal flow from P to I. Also, since this is the only way to reach node I, pI = pPItot.

pI is the true probability of reaching node I since node I is terminal, no bouncing, no repetitions possible. This is true of all terminal nodes I,J,G,H,X,Y.
pQPtot = pPItot = pI
pQ/3 - pP/2 = pP/2
pQ/3 = pP
pI = pP/2 = pQ/6

pJ = pQJtot = pQ*pQJ - 0 = pQ/3

Another flow conservation equation:
(This is not entirely unlike Kirchhoff's current law for electrical circuits)

pAQtot = pI + pJ
pA/2 - pQ/3 = pQ/6 + pQ/3
3/6*pA = pQ(1/6 + 2/3) = 5/6*pQ  <=>  3*pA = 5*pQ  <=>  pQ = 3/5*pA
pI = pA/10
pJ = pA/5

By symmetry, R and C behave as P and Q:

pC/3 = pR
pY = pRYtot = pR/2 = pC/6
pCFtot = pC*pCF - 0 = pC/3  { Note however that pF will be something else }
pBDtot = pB*pBD - 0 = pB/3  { Note however that pD will be something else }

pBCtot = pB*pBC - pC*pCB
pBCtot = pCFtot + pY
pB/3 - pC/3 = pC/3 + pC/6
2*pB = 2*pC + 2*pC + pC = 5*pC  <=>  pC = 2/5*pB

pABtot = pA*pAB - pB*pBA
pABtot = pBDtot + pCFtot + pY
pA/2 - pB/3 = pB/3 + pC/3 + pC/6
pA/2 = 2/3*pB + pC/2 = 2/3*pB + pB/5 = pB(10/15 + 3/15) = pB(13/15)
pB = 15/26*pA
pY = pC/6 = 2/30*pB = pB/15 = pA/26
pCFtot = pC/3 = 2*pY = 2/26*pA = pA/13
pBDtot = pB/3 = 5/26*pA

Eventually we have to go down one of the five pitfalls:

1 = pI + pJ + pBDtot + pCFtot + pY
1 = pA(1/10 + 1/5 + 5/26 + 1/13 + 1/26) = pA(3/10 + 8/26) = pA(3/10 + 4/13) =
  = pA(3*13 + 4*10)/(10*13) = 79/130*pA
pA = 130/79  { > 1 as already established }

pI = pA/10 =                         13/79
pJ = pA/5  =                         26/79
pBDtot = 5/26*pA = (5*130)/(26*79) = 25/79
pCFtot = pA/13 =                     10/79
pY = pA/26 =                          5/79

Now we move to "stage 2" to find pG, pH, pX.

pG = pDGtot = pD*pDG = pD/2
pH = pEHtot = pE*pEH = pE/3
pX = pFXtot = pF*pFX = pF/2

pDEtot = pD*pDE - pE*pED = pD/2 - pE/3
pFEtot = pF*pFE - pE*pEF = pF/2 - pE/3

Flow equations:

pBDtot = pDGtot + pDEtot
25/79 = pD/2 + pD/2 - pE/3 = pD - pE/3

pCFtot = pFXtot + pFEtot
10/79 = pF/2 + pF/2 - pE/3 = pF - pE/3

pEHtot = pDEtot + pFEtot
pE/3 = pD/2 - pE/3 + pF/2 - pE/3  <=>  2*pE = pD + pF
2*pE = pD + pF = 35/79 + 2/3*pE 
4/3*pE = 35/79
pE = (3*35)/(4*79) =                 105/316
pD = 25/79 + pE/3 = 25/79 + 35/316 = 135/316
pF = 10/79 + pE/3 = 10/79 + 35/316 =  75/316

pG = pD/2 = 135/632
pH = pE/3 =  35/316
pX = pF/2 =  75/632

Finally:

p_WIN = pX + pY = 75/632 + 5/79 = (75 + 5*8)/632 = 115/632  { ~= 1/6 }
p_WIN ~= 0.18196


Solution to worst-case interpretation (I1) using David Jones' method:
--------------------------------------------------------------------

Letter Z denotes probability to win at node Z.

I = J = G = H = 0
X = Y = 1
R = 1/2*Y + 1/2*C = 1/2 + C/2          <=>  2R = 1 + C
C = 1/3*B + 1/3*F + 1/3*R
B = 1/3*A + 1/3*D + 1/3*C
F = 1/2*X + 1/2*E = 1/2 + E/2          <=>  2F = 1 + E
E = 1/3*D + 1/3*H + 1/3*F = D/3 + F/3  <=>  3E = D + F
D = 1/2*G + 1/2*E = E/2                <=>  2D = E
                                            6E = 2D + 2F = E + 2F
                                            5E = 2F = 1 + E
                                            4E = 1  <=>  E = 1/4
E = 1/4
D = E/2 = 1/8
F = 1/2 + E/2 = 1/2 + 1/8 = 5/8
C = B/3 + 5/24 + R/3
6C = 2B + 5/4 + 2R = 2B + 5/4 + 1 + C  <=>  5C = 2B + 9/4
B = A/3 + 1/24 + C/3
5C - 9/4 = 2B = 2A/3 + 1/12 + 2C/3
15C - 27/4 = 2A + 1/4 + 2C
13C = 2A + 1/4 + 27/4 = 2A + 7

P = 1/2*I + 1/2*Q = Q/2                <=>  2P = Q
Q = 1/3*P + 1/3*J + 1/3*A = P/3 + A/3  <=>  3Q = P + A
                                            6Q = 2P + 2A = Q + 2A
                                            5Q = 2A
A = 1/2*Q + 1/2*B
10A = 5Q + 5B = 2A + 5B                <=>  8A = 5B
3B = A + 1/8 + C
24A = 15B = 5A + 5/8 + 5C              <=>  19A = 5C + 5/8

We now have the two-equation system
13C = 2A + 7     <=>  5*13C = 10A + 35
19A = 5C + 5/8   <=>  13*19A = 5*13C + 13*5/8

13*19A = 10A + 35 + 13*5/8
A(13*19 - 10) = 35 + 65/8 = 35 + (64 + 1)/8 = 43 + 1/8
13*19 = 13(20 - 1) = 260 - 13 = 247
237*A = 43 + 1/8 = (43*8 + 1)/8 = 345/8

A = 345/(8*237) = (115*3)/(8*79*3) = 115/(8*79) = 115/632
A ~= 0.18196
How nice, we have now reached the same result with two different approaches. This suggests that both methods are valid.

Solution to next-worst-case interpretation (I2):
-----------------------------------------------


David Jones' submitted analysis differs from my interpretation I1 only in that node A is not regarded as a junction after the first fall.

See David Jones' analysis (although I have not double-checked it);

A = 161/880 ~= 0.183

If you would also consider corners as no choice, see next section.

Solution to limiting interpretation (I3):
----------------------------------------
Now let's also investigate a more strictly limiting interpretation of when there is a "choice";

Backtracking allowed but only where there is an "effective" choice.

In this interpretation, corners represent no choice. Corners are simply passed just as a straight corridor. Also junctions where no forking is allowed represent no choice. Thus nodes A, D and F are effective junctions only when falling down, otherwise A is seen as a simple corridor and D and F are seen as simple corners.

Nodes P and R disappear as junctions, and nodes A, D and F disappear unless you fall from above.

I think Davy's method will be the most convenient now. Letter Z denotes probability to win at node Z.
I = J = G = H = 0
X = Y = 1
C = 1/3*B + 1/3*F + 1/3*Y = B/3 + F/3 + 1/3
B = 1/3*Q + 1/3*D + 1/3*C
F = 1/2*X + 1/2*E = 1/2 + E/2
E = 1/3*G + 1/3*H + 1/3*X = 1/3
D = 1/2*G + 1/2*E = E/2 =   1/6
F = 1/2 + 1/6 = 4/6 =       2/3

C = B/3 + F/3 + 1/3 = B/3 + 2/9 + 1/3 = B/3 + 5/9
B = Q/3 + (1/3)*(1/6) + C/3 = Q/3 + C/3 + 1/18
3B = Q + 1/6 + C = Q + 1/6 + B/3 + 5/9
B(9 - 1)/3 = Q + (3 + 10)/18
8/3*B = Q + 13/18                      <=>  6*8B = 18Q + 13

Q = 1/3*I + 1/3*J + 1/3*B = B/3        <=>  3Q = B
                                            18Q = 6B
48B = 6B + 13  <=>  42B = 13  <=>  B = 13/42
Q = B/3 = 13/126

A = 1/2*Q + 1/2*B = B/6 + B/2 = 2/3*B = (2*13)/(3*42) = 13/(3*21) =
  = 13/63
A ~= 0.2063


Solution to trivial interpretation (I4):
---------------------------------------

With no backtracking allowed,
there are multiple ways to reach the simple solution
A = 1/4 = 0.25
as many have shown already.

This is the highest result you can get with any "reasonable"
interpretation of the problem.

Suggestions that A may be as large as 0.4 are not valid.




Return to Cliff Pickover's home page which includes computer art, educational puzzles, higher dimensions, fractals, virtual caverns, JAVA/VRML, alien creatures, black hole artwork, and animations. Click here for a complete list of over 20 Cliff Pickover books.