wu :: forums « wu :: forums - Tunnels of Callicrates » Welcome, Guest. Please Login or Register. Nov 28th, 2022, 7:09am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: SMQ, ThudnBlunder, william wu, towr, Grimbal, Icarus, Eigenray)    Tunnels of Callicrates « Previous topic | Next topic »
 Pages: 1 2 Reply Notify of replies Send Topic Print
 Author Topic: Tunnels of Callicrates  (Read 6148 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:
 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

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

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

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

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

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
Sir Col
Uberpuzzler

impudens simia et macrologus profundus fabulae

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

Thanks, visitor, all corrected (I think).
 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 #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

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

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »