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

        riddles >> hard >> Tunnels of Callicrates
        
(Message started by: THUDandBLUNDER on May 23rd, 2003, 7:32am)
Title: Tunnels of Callicrates
Post by THUDandBLUNDER on May 23rd, 2003, 7:32am
http://sprott.physics.wisc.edu/pickover/maze1.gif

In the diagram above one enters the tunnels at Start. With equal probability one one can move downwards,
left, or right. One can never move upwards. That is, each time you have a choice of tunnels, you are equally
likely to choose either route. What is the chance that you will emerge at the exit marked Win?
Title: Re: Tunnels of Callicrates
Post by visitor on May 23rd, 2003, 8:21am
Clarification: can one never move upwards at all, or is it just that at an intersection one can not choose to turn upwards?
If it's the former, the left half of the diagram is completely pointless.
Title: Re: Tunnels of Callicrates
Post by THUDandBLUNDER on May 23rd, 2003, 8:44am
The former.  

And you may consider the two cases where back-tracking is

a) allowed
b) not allowed
Title: Re: Tunnels of Callicrates
Post by wowbagger on May 30th, 2003, 8:40am

on 05/23/03 at 08:44:19, THUDandBLUNDER wrote:
The former.
 
In this case, as visitor already pointed out, the left half is of no use in arriving at "Win".


Quote:
And you may consider the two cases where back-tracking is
a) allowed
b) not allowed

Hm, by "back-tracking", do you mean using an edge more than once? Genuine loops are precluded as we mustn't turn upwards, so I assume the following meaning:
In case a) we can turn around and simply go back to where we came from, while in case b) we can't.

My first calculation gives
   P = [hide] 3 / 16 [/hide]
for case b).
Title: Re: Tunnels of Callicrates
Post by THUDandBLUNDER on May 30th, 2003, 9:02am
AMERICAN HERITAGE DICTIONARY:

back·track (bČk“trČk”) intr.v. back·tracked, back·track·ing, back·tracks.
1. To go back over the course by which one has come.

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

I get [hide]p = 1/4[/hide]

Title: Re: Tunnels of Callicrates
Post by wowbagger on May 30th, 2003, 10:10am
What I suppose should be phonetics looks like double Dutch in my browser. Definitely my browser's fault.

Do we at least agree on there being six paths?
Title: Re: Tunnels of Callicrates
Post by THUDandBLUNDER on May 30th, 2003, 10:28am

Quote:
What I suppose should be phonetics looks like double Dutch in my browser. Definitely be my browser's fault.

Perhaps its default language is German - or single Dutch?

As few people have shown any interest in this puzzle, we may as well put it to bed:


Quote:
Do we at least agree on there being six paths? ]

Agreed. Also, 1/8 of the time you get to the top-right corner and win. Agreed?
Title: Re: Tunnels of Callicrates
Post by wowbagger on May 30th, 2003, 10:31am

on 05/30/03 at 10:28:20, THUDandBLUNDER wrote:
As few people have shown any interest in this puzzle, we may as well put it to bed

Give it a little more time. Or me.
Oh well, we can wake it up again later anyway.


Quote:
Agreed. Also, 1/8 of the time you get to the top-right corner and win. Agreed?

Yep.
Title: Re: Tunnels of Callicrates
Post by Chronos on Jun 1st, 2003, 2:17pm

Quote:
Also, 1/8 of the time you get to the top-right corner and win. Agreed?
Not necessarily, in the no-backtrack case.  If, in the intersection just above "win", you go left, you'll be stuck.
Title: Re: Tunnels of Callicrates
Post by wowbagger on Jun 2nd, 2003, 4:59am
I think you're right, Chronos. 1/8 is the probability of getting to the top-right corner. From there, p(Win) = 3/4.
Title: Re: Tunnels of Callicrates
Post by Sir Col on Jun 3rd, 2003, 4:36pm
Using the numbered diagram:
http://mathschallenge.net/images/maze1.gif

I get
:: [hide]P(12456789)=(1/2)6=1/64 (decision points: 1,2,4,5,7 and 9 [avoiding getting stuck])
P(1245679)=(1/2)5=1/32 (decision points: 1,2,4,5 and 7)
P(1236789)=(1/2)6=1/64 (decision points: 1,2,3,6,7 and 9 [avoiding getting stuck])
P(123679)=(1/2)5=1/32 (decision points: 1,2,3,6 and 7)
P(123879)=(1/2)4=1/16 (decision points: 1,2,3 and 8)
P(12389)=(1/2)5=1/32 (decision points: 1,2,3,8 and 9 [avoiding getting stuck])

Therefore, P(win)=3/16 [/hide]::
Title: Re: Tunnels of Callicrates
Post by visitor on Jun 3rd, 2003, 6:30pm
Sir, you missed a couple (going from 3 to 8), and in your second path, 6 is not a decision point.

Thud, I still need a clarification on "backtrack." Where are you allowed to turn around? At all intersections? At only those intersections where you have a choice of directions? At corners where the path turns but no decisions are made? If all turns and intersections are backtrack points, I get 18.3% wins.
Title: Re: Tunnels of Callicrates
Post by Sir Col on Jun 4th, 2003, 12:30am
Thanks, visitor, all corrected (I think).  ;)
Title: Re: Tunnels of Callicrates
Post by THUDandBLUNDER on Jun 4th, 2003, 2:17am
The idea of the puzzle is to imagine that you are a 'mindless marble', always falling down or going right or left
(but not up). The marble keeps going until it reaches one of the four exits. Hence, back-tracking (when allowed) is always possible, even at points 3 and 5.
Title: Re: Tunnels of Callicrates
Post by Sir Col on Jun 4th, 2003, 4:32am
Are you saying that at a point, like 2 and 3, P(Left)=P(Down)=P(Right)=1/3? In which case, we are dealing with a converging infinite probability series between 2 and 3; for example, P(12323232323....) is a possible route?
Title: Re: Tunnels of Callicrates
Post by THUDandBLUNDER on Jun 4th, 2003, 6:22am
Yes Sir, that is how I interpret the problem.
Title: Re: Tunnels of Callicrates
Post by Sir Col on Jun 4th, 2003, 8:11am
Which explains why it is in the hard section! Back to the pencil and paper, and copious amounts of tea and chocolate...

BTW, nice problem, T&B.
Title: Re: Tunnels of Callicrates
Post by towr on Jun 4th, 2003, 9:52am
make a markov model (states and transitions) from it and it's pretty easy to compute numerically..
Title: Re: Tunnels of Callicrates
Post by towr on Jun 5th, 2003, 4:06am
If 1 is also a point were you can turn, then I get [hide]0.181962025316455[/hide]
If 1 isn't a turnpoint I get [hide]0.1796875[/hide] (after you go from 1 it isn't really different from the tunnels between points, since you can't go up again anyway)
Title: Re: Tunnels of Callicrates
Post by THUDandBLUNDER on Jun 13th, 2003, 1:05pm

Quote:
If 1 is also a point were you can turn...

Yes, I consider 1 to be a turn point. Also, two turn points are not enumerated on Sir Col's diagram.
Title: Re: Tunnels of Callicrates
Post by Sir Col on Jun 23rd, 2003, 9:25am
Where? Are you saying that at the intersection leading down, to the left of 1, you can arrive and return with probability 1/3? Surely there is no decision at the top right and top left L bend?
Title: Re: Tunnels of Callicrates
Post by somebody on Jan 12th, 2004, 9:15am
Here is the solution when backtracking is allowed:

Intersection numbers are as in Sir Col's post, with the addition of intersection #10 to the left of #1.
I am assuming that corners don't count as intersections (so if you go right from 3 you always get to 8).
[hide]
P(n) means the probability of winning if you start at intersection #n.

P(7)=P(8)=P(9)=1
P(all unnumbered intersections)=0

P(6)= 1/2 * P(7) + 1/2 * P(5) = 1/2 + 1/2 * P(5)
P(5)=1/3 * P(6) + 1/3 * 0 + 1/3 * P(4) = 1/3 * P(6) + 1/3 * P(4)
P(4)=1/2 * P(5) + 1/2 * 0 = 1/2 * P(5)

Solving the 3 equations gives: P(4)=1/8, P(5)=1/4, P(6)=5/8

P(3)=1/3 * P(8) + 1/3 * P(6) + 1/3 * P(2) = 13/24 + 1/3 * P(2)
P(2)=1/3 * P(3) + 1/3 * P(4) + 1/3 * P(1) = 1/24 + 1/3 * P(3) + 1/3 * P(1)
P(1)=1/2 * P(2) + 1/2 * P(10)
P(10)=1/3 * P(1) + 1/3 * 0 + 1/3 * 0 = 1/3 * P(1)

Solving gives: P(3) = 161/248, P(2)=10/31, P(10)=2/31[/hide]
And the answer: [hide]P(1) = 6/31[/hide]
Title: Re: Tunnels of Callicrates
Post by Sir Col on Jan 13th, 2004, 12:30am
I'd forgotten about this problem. What a clever solution, somebody!  8)
Title: Re: Tunnels of Callicrates
Post by Sir_Rogers on Jun 19th, 2007, 3:10am
I found a different result for b) when backtracking isn't allowed.

I attached a picture for further clearing up things. Each of the circle is a point where a decision has to be made. There's 6 in total that could possibly lead to the exit win.

Now as no backtracking is allowed, the probability of chosing the way towards "Win" is 0.5.

Now there is only 3 possible ways through these 6 circles:

1) 1-2-3
2) 1-2-3-6
3) 1-2-4-5-6

Now the longest way only uses 5 of the circles, so if we count the total probability to get to the exit "Win", I get:

1/32 + 2/32 + 4/32 = 7/32

Which is different from the solution that the original poster has suggested: 1/4 = 8/32

I don't think I've made a mistake somewhere, but I'm open to corrections/suggestions/questions ...

any ideas? :-)
Title: Re: Tunnels of Callicrates
Post by Sir_Rogers on Jun 19th, 2007, 3:14am
Hmm I just realized something ... at the last junction ... if you come from above and decide to go left, would that be a dead-end?

If so, then I'd have to change the probabilities with the first one being 1) 1-2-3-7, so that would end up with 2/32 + 2/32 + 4/32 = 1/8

Now I don't know how you interpret the situation, whether the thing would become stuck or what?
Title: Re: Tunnels of Callicrates
Post by rmsgrey on Jun 19th, 2007, 7:18am

on 06/19/07 at 03:10:16, Sir_Rogers wrote:
3) 1-2-4-5-6

Now the longest way only uses 5 of the circles

What options do you have at 6 when you arrive from 5?
Title: Re: Tunnels of Callicrates
Post by Hippo on Jun 19th, 2007, 10:52am
I can read this problem several ways, it seems is not well formulated.
The variants depend on answers to following questions:

1) When you arive to "L" (no crossing) place from right ...
a) you continue up (with prob=1)
b) you return (with prob=1)
c) your path ends here (with prob 1)

2) When you arrive to T from left
a) you go down with prob=1/2 you continue right with prob=1/2
b) you go down with prob 1/3, left with 1/3 and right with 1/3

3) When you arrive to T from buttom (1a) case
a) go left with prob=1/2, go right with prob=1/2
b) go left with prob=1/3, go right with prob=1/3 and go down with prob=1/3

4) When you arrive to "+ with missing left" from right
a) go down with prob=1
b) go down with prob 1/2 and right with prob 1/2

5) When you arrive to "+ with missing left" from bottom (1a) case)
a) go right with prob 1
b) go down with prob 1/2, go right with prob 1/2

6) When you arrive to "+ with missing left" from top
a) go right with prob 1/2 and down with prob 1/2.

(Suppose right-left symmetry)

I suppose 1a) 2a) 3a) 4a) 5a) 6a) case is the basic variant and 1a) 2b) 3b) 4b) 5b) 6a) is the backtrack variant.

The basic variant is easier ...
Number all crossings left to right from top to bottom starting with 0 to extend Sir_Rogers notation.
Denote wxtop winning probability when arriving to vertex x from top, similarly
for bot,rt,lft. We can start with w14lft=1, w13rt=0,
w12rt=0, w7rt=0.

Continue with easiest equations: w14top=1/2+1/2 w10bot=
1/2+1/2 w11lft=
1/2+1/2w14top.
Therefore w14top=1
=w10bot=w11lft.
Now w10top=
1/2(w11lft+w14lft)=1 and similarly
w11top=
1/2(w10rt+w14top)=
1/2(w14lft+w14top)=1.

Follow with more complicated equations:
w13top=
0+1/2w5bot=
1/4w4rt+1/4w6lft=
1/4w9top+1/4w10top=
1/8w12rt+1/8w13top+1/4=
0+1/8w13top+1/4.
Therefore 7/8 w13top=1/4 and w13top=2/7,
w4rt=
w9top=1/7,

Now w12top=
0+1/2w9lft=
1/2w9top=1/14 and
w8lft=
w12top=1/14 and
w7top=
0+1/2w8lft=1/28.

Similarly w8top=
0+1/2w12top=
1/2w8lft=1/28.

Now w0rt=
1/2(w7top+w8top)=1/28.

Now w6top=
1/2w5rt+1/2=
1/4w4rt+0+1/2=15/28 and
w4top=
1/2w9top+1/2w5lft=
1/14+1/4=18/56.

Finaly w3lft=
1/2(w6top+1)=
43/56 and w2lft=
1/2w4top+1/2w3lft=
61/112 and w1top=
1/2w0rt+1/2w2lft=
69/224.
Title: Re: Tunnels of Callicrates
Post by Sir_Rogers on Jun 19th, 2007, 11:21am
Erm ... your assumptions are flawed, because it says you can't go up, and there's two different solutions, one for backtracking and one for none.

Backtracking means you can go back to where you came from ...

I'm just not sure about the dead end one. Any ideas?
That would throw my results all over ..
Title: Re: Tunnels of Callicrates
Post by ThudanBlunder on Jun 19th, 2007, 12:49pm
I first saw the problem here (http://sprott.physics.wisc.edu/pickover/tunnel.html).
Title: Re: Tunnels of Callicrates
Post by Grimbal on Jun 20th, 2007, 1:39am

on 06/19/07 at 03:10:16, Sir_Rogers wrote:
1) 1-2-3
2) 1-2-3-6
3) 1-2-4-5-6

In
3) 1-2-4-5-6
you have no choice at 6, so the probability is 1/16.

And the problem of the last junction right needs clarification before giving an answer.  I'd say if the marble gets stuck, it should count as a loss.
Title: Re: Tunnels of Callicrates
Post by Hippo on Jun 20th, 2007, 4:25am

on 06/19/07 at 11:21:18, Sir_Rogers wrote:
Erm ... your assumptions are flawed, because it says you can't go up, and there's two different solutions, one for backtracking and one for none.

Backtracking means you can go back to where you came from ...


OK, so what are the options for which you are solving the problem?
No backtracking is inconsistent in 1b) case, too (at least if I understand backtracking well). The 1c) case does not correspond to "marble" interpretation.

If 1a) is not correct choice, there is only one consistent variant ... 1b) 2b) 3b) 4b) 5b) 6a).
Do we agree?

For the 1b) 2b) 3b) 4b) 5b) 6a) case the situation is much more easier. We neednot distinguish the direction from which we arrived.
w14=1, w13=0, w12=0
The bar from 10 to 11 does not play any role ... (an easy equation) w11=1/2w10+1/2w14=
1/4w11+3/4w14=1/4w11+3/4 and we get
w11=1=w10.
Furthermore w9=1/2w12+1/2w13=0, w8=w12=0,
and w7=0+1/2w8=0.

Now the interesting part begins
w5=1/3w4+1/3w13+1/3w6=1/6w9+1/6w5+0+1/6w5+1/6w10=
0+1/3w5+1/6 and therefore w5=3/2*1/6=1/4, w6=5/8, and w4=1/8.

Finaly w2=1/3w0+1/3w4+1/3w3=
1/9w7+1/9w8+1/9w2+
1/24+1/9w2+1/9w6+1/9w11=
0+0+2/9w2+1/24+5/72+1/9 and w2=9/7*(1/24+5/72+1/9)=2/7, w0=1/3w2=2/21,
and w3=1/3w2+1/3w6+1/3w11=2/21+5/24+1/3=107/168.
w1=1/2w0+1/2w2=1/21+107/336=123/336

oops ... I've used w3 instead of  w2. Correct answer is 1/21+1/7=4/21.
Title: Re: Tunnels of Callicrates
Post by Wardub on Apr 8th, 2008, 12:03am
What about the probability if back tracking isn't allowed but you can move upward.  Also assume you start moving down from the top.  So at the first intersection you can only move left or right.
This lets solutions like  left, down, right, up, right, up, right, right, down, down, right, down.  I believe I have the answer.  
[hide] .102996826 or 3375/32768.  I found 48 unique paths.  I also found it interesting that the probability lowered when you allowed moving up.  
I think this is because at the last intersection right before the end.  There is always a 50% chance you take the wrong path and end up stopped.[/hide]

Could someone check my answer, there is a high chance I did something wrong.

Also could someone clarify something about backtracking allowed.  When backtracking is allowed.  Can you go up?  If so wouldn't you eventually end at the win place?


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