wu :: forums
« wu :: forums - Tunnels of Callicrates »

Welcome, Guest. Please Login or Register.
Dec 15th, 2018, 3:03am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Eigenray, william wu, ThudnBlunder, Grimbal, Icarus, SMQ, towr)
   Tunnels of Callicrates
« Previous topic | Next topic »
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Tunnels of Callicrates  (Read 5349 times)
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Tunnels of Callicrates  
« on: May 23rd, 2003, 7:32am »
Quote Quote Modify Modify


 
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?
 
« Last Edit: May 23rd, 2003, 7:34am by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
visitor
Guest

Email

Re: Tunnels of Callicrates  
« Reply #1 on: May 23rd, 2003, 8:21am »
Quote Quote Modify Modify Remove Remove

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.
IP Logged
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Tunnels of Callicrates  
« Reply #2 on: May 23rd, 2003, 8:44am »
Quote Quote Modify Modify

The former.  
 
And you may consider the two cases where back-tracking is  
 
a) allowed
b) not allowed
« Last Edit: Jun 4th, 2003, 2:40am by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
wowbagger
Uberpuzzler
*****





242002184 242002184    


Gender: male
Posts: 727
Re: Tunnels of Callicrates  
« Reply #3 on: May 30th, 2003, 8:40am »
Quote Quote Modify Modify

on May 23rd, 2003, 8:44am, 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 = 3 / 16
for case b).
« Last Edit: May 30th, 2003, 8:42am by wowbagger » IP Logged

"You're a jerk, <your surname>!"
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Tunnels of Callicrates  
« Reply #4 on: May 30th, 2003, 9:02am »
Quote Quote Modify Modify

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 p = 1/4  
 
« Last Edit: May 30th, 2003, 9:21am by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
wowbagger
Uberpuzzler
*****





242002184 242002184    


Gender: male
Posts: 727
Re: Tunnels of Callicrates  
« Reply #5 on: May 30th, 2003, 10:10am »
Quote Quote Modify Modify

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?
« Last Edit: May 30th, 2003, 10:14am by wowbagger » IP Logged

"You're a jerk, <your surname>!"
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Tunnels of Callicrates  
« Reply #6 on: May 30th, 2003, 10:28am »
Quote Quote Modify Modify

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

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
wowbagger
Uberpuzzler
*****





242002184 242002184    


Gender: male
Posts: 727
Re: Tunnels of Callicrates  
« Reply #7 on: May 30th, 2003, 10:31am »
Quote Quote Modify Modify

on May 30th, 2003, 10:28am, 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.
IP Logged

"You're a jerk, <your surname>!"
Chronos
Full Member
***





   
WWW Email

Gender: male
Posts: 288
Re: Tunnels of Callicrates  
« Reply #8 on: Jun 1st, 2003, 2:17pm »
Quote Quote Modify Modify

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





242002184 242002184    


Gender: male
Posts: 727
Re: Tunnels of Callicrates  
« Reply #9 on: Jun 2nd, 2003, 4:59am »
Quote Quote Modify Modify

I think you're right, Chronos. 1/8 is the probability of getting to the top-right corner. From there, p(Win) = 3/4.
IP Logged

"You're a jerk, <your surname>!"
Sir Col
Uberpuzzler
*****




impudens simia et macrologus profundus fabulae

   
WWW

Gender: male
Posts: 1825
Re: Tunnels of Callicrates  
« Reply #10 on: Jun 3rd, 2003, 4:36pm »
Quote Quote Modify Modify

Using the numbered diagram:

 
I get
:: 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
::
« Last Edit: Jun 4th, 2003, 12:29am by Sir Col » IP Logged

mathschallenge.net / projecteuler.net
visitor
Guest

Email

Re: Tunnels of Callicrates  
« Reply #11 on: Jun 3rd, 2003, 6:30pm »
Quote Quote Modify Modify Remove Remove

Sir, you missed a couple (going from 3 to Cool, 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.
IP Logged
Sir Col
Uberpuzzler
*****




impudens simia et macrologus profundus fabulae

   
WWW

Gender: male
Posts: 1825
Re: Tunnels of Callicrates  
« Reply #12 on: Jun 4th, 2003, 12:30am »
Quote Quote Modify Modify

Thanks, visitor, all corrected (I think).  Wink
IP Logged

mathschallenge.net / projecteuler.net
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Tunnels of Callicrates  
« Reply #13 on: Jun 4th, 2003, 2:17am »
Quote Quote Modify Modify

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.
 
« Last Edit: Jun 4th, 2003, 3:05am by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
Sir Col
Uberpuzzler
*****




impudens simia et macrologus profundus fabulae

   
WWW

Gender: male
Posts: 1825
Re: Tunnels of Callicrates  
« Reply #14 on: Jun 4th, 2003, 4:32am »
Quote Quote Modify Modify

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

mathschallenge.net / projecteuler.net
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Tunnels of Callicrates  
« Reply #15 on: Jun 4th, 2003, 6:22am »
Quote Quote Modify Modify

Yes Sir, that is how I interpret the problem.
« Last Edit: Jun 4th, 2003, 11:43am by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
Sir Col
Uberpuzzler
*****




impudens simia et macrologus profundus fabulae

   
WWW

Gender: male
Posts: 1825
Re: Tunnels of Callicrates  
« Reply #16 on: Jun 4th, 2003, 8:11am »
Quote Quote Modify Modify

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.
« Last Edit: Jun 4th, 2003, 8:12am by Sir Col » IP Logged

mathschallenge.net / projecteuler.net
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13651
Re: Tunnels of Callicrates  
« Reply #17 on: Jun 4th, 2003, 9:52am »
Quote Quote Modify Modify

make a markov model (states and transitions) from it and it's pretty easy to compute numerically..
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13651
Re: Tunnels of Callicrates  
« Reply #18 on: Jun 5th, 2003, 4:06am »
Quote Quote Modify Modify

If 1 is also a point were you can turn, then I get 0.181962025316455
If 1 isn't a turnpoint I get 0.1796875 (after you go from 1 it isn't really different from the tunnels between points, since you can't go up again anyway)
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Tunnels of Callicrates  
« Reply #19 on: Jun 13th, 2003, 1:05pm »
Quote Quote Modify Modify

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

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
Sir Col
Uberpuzzler
*****




impudens simia et macrologus profundus fabulae

   
WWW

Gender: male
Posts: 1825
Re: Tunnels of Callicrates  
« Reply #20 on: Jun 23rd, 2003, 9:25am »
Quote Quote Modify Modify

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

mathschallenge.net / projecteuler.net
somebody
Guest

Email

Re: Tunnels of Callicrates  
« Reply #21 on: Jan 12th, 2004, 9:15am »
Quote Quote Modify Modify Remove Remove

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

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

And the answer: P(1) = 6/31
IP Logged
Sir Col
Uberpuzzler
*****




impudens simia et macrologus profundus fabulae

   
WWW

Gender: male
Posts: 1825
Re: Tunnels of Callicrates  
« Reply #22 on: Jan 13th, 2004, 12:30am »
Quote Quote Modify Modify

I'd forgotten about this problem. What a clever solution, somebody!  Cool
IP Logged

mathschallenge.net / projecteuler.net
Sir_Rogers
Newbie
*





   


Posts: 4
Re: Tunnels of Callicrates   maze1.gif
« Reply #23 on: Jun 19th, 2007, 3:10am »
Quote Quote Modify Modify

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

Sir_Rogers
Newbie
*





   


Posts: 4
Re: Tunnels of Callicrates  
« Reply #24 on: Jun 19th, 2007, 3:14am »
Quote Quote Modify Modify

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?
IP Logged
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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