Author |
Topic: Tunnels of Callicrates (Read 6334 times) |
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
 |
Tunnels of Callicrates
« on: May 23rd, 2003, 7:32am » |
 Quote  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
|
|
Re: Tunnels of Callicrates
« Reply #1 on: May 23rd, 2003, 8:21am » |
Quote Modify
 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:
Posts: 4489
|
|
Re: Tunnels of Callicrates
« Reply #2 on: May 23rd, 2003, 8:44am » |
Quote 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
 
Gender:
Posts: 727
|
|
Re: Tunnels of Callicrates
« Reply #3 on: May 30th, 2003, 8:40am » |
Quote Modify
|
on May 23rd, 2003, 8:44am, THUDandBLUNDER wrote:
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:
Posts: 4489
|
|
Re: Tunnels of Callicrates
« Reply #4 on: May 30th, 2003, 9:02am » |
Quote Modify
|
AMERICAN HERITAGE DICTIONARY:
back·track (bČktrČ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
Gender:
Posts: 727
|
|
Re: Tunnels of Callicrates
« Reply #5 on: May 30th, 2003, 10:10am » |
Quote 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:
Posts: 4489
|
|
Re: Tunnels of Callicrates
« Reply #6 on: May 30th, 2003, 10:28am » |
Quote 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
Gender:
Posts: 727
|
|
Re: Tunnels of Callicrates
« Reply #7 on: May 30th, 2003, 10:31am » |
Quote 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
Gender:
Posts: 288
|
|
Re: Tunnels of Callicrates
« Reply #8 on: Jun 1st, 2003, 2:17pm » |
Quote 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
Gender:
Posts: 727
|
|
Re: Tunnels of Callicrates
« Reply #9 on: Jun 2nd, 2003, 4:59am » |
Quote 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
Gender:
Posts: 1825
|
|
Re: Tunnels of Callicrates
« Reply #10 on: Jun 3rd, 2003, 4:36pm » |
Quote 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
|
|
Re: Tunnels of Callicrates
« Reply #11 on: Jun 3rd, 2003, 6:30pm » |
Quote Modify
Remove
|
Sir, you missed a couple (going from 3 to  , 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 |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Tunnels of Callicrates
« Reply #13 on: Jun 4th, 2003, 2:17am » |
Quote 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
Gender:
Posts: 1825
|
|
Re: Tunnels of Callicrates
« Reply #14 on: Jun 4th, 2003, 4:32am » |
Quote 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:
Posts: 4489
|
|
Re: Tunnels of Callicrates
« Reply #15 on: Jun 4th, 2003, 6:22am » |
Quote 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
Gender:
Posts: 1825
|
|
Re: Tunnels of Callicrates
« Reply #16 on: Jun 4th, 2003, 8:11am » |
Quote 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:
Posts: 13730
|
|
Re: Tunnels of Callicrates
« Reply #17 on: Jun 4th, 2003, 9:52am » |
Quote 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:
Posts: 13730
|
|
Re: Tunnels of Callicrates
« Reply #18 on: Jun 5th, 2003, 4:06am » |
Quote 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:
Posts: 4489
|
|
Re: Tunnels of Callicrates
« Reply #19 on: Jun 13th, 2003, 1:05pm » |
Quote 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
Gender:
Posts: 1825
|
|
Re: Tunnels of Callicrates
« Reply #20 on: Jun 23rd, 2003, 9:25am » |
Quote 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
|
|
Re: Tunnels of Callicrates
« Reply #21 on: Jan 12th, 2004, 9:15am » |
Quote Modify
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
Gender:
Posts: 1825
|
|
Re: Tunnels of Callicrates
« Reply #22 on: Jan 13th, 2004, 12:30am » |
Quote Modify
|
I'd forgotten about this problem. What a clever solution, somebody!
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Sir_Rogers
Newbie
Posts: 4
|
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? 
|
|
IP Logged |
 |
|
|
Sir_Rogers
Newbie
Posts: 4
|
|
Re: Tunnels of Callicrates
« Reply #24 on: Jun 19th, 2007, 3:14am » |
Quote 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print