Author |
Topic: The ASYLUM (Read 3713 times) |
|
mattian
Senior Riddler
 
Gender: 
Posts: 404
|
ASYLUM
======
You are the only patient in a mental asylum with eight wards labeled A through H. Each ward has four doors - three white and one red. The white doors are marked, "1", "2" and "3". Although these markings are not very helpful, you do know that each door leads to one of three places - the previous ward, the next ward or the ward in which you're already standing.
The terms "previous" and "next" in this case refer to those wards with ward letters alphabetically before and after the current ward letter. For example: If door 1 in ward C leads to the next ward, then it leads to ward D. If door 2 leads to the previous ward it leads to B. If door 3 of ward H leads to the next ward, then it leads to ward A, and vice versa. In other words, the ward-connections wrap around.
When you walk through a white door, you enter the destination ward through the red door of the that ward. The red door locks behind you.
Your objective is to escape the asylum and you know that you can do that by turning around going back through the red door that locked behind you.
* Unfortunately the red doors are all locked.
* Fortunately during your journey from ward to ward, in one of the wards you find a key.
* Unfortunately if you use the key, you will set off the alarm and be caught, restrained and returned to your room.
* Fortunately you know that the alarm in ward E has been disabled.
* Unfortuantely you never know which ward you're in - except in the very beginning: Ward A.
Objective: Escape the asylum in the fewest transitions possible. Remember you may only use the key once - so make sure you know you're in Ward E when you do it.
Some things to think about:
Is it possible to guarantee an escape?
Is it possible to guarantee that the patient will find the key - given a particular strategy?
Some rules:
1. The only way to see what's behind a door is to walk through it, and close the door behind you.
2. All wards look identical
3. A transition is counted each time a white door is opened.
I have written a little simulator which lets you be the patient in this puzzle. Please visit http://www.monahansen.com/asylum/
Note: Currently only IE support has been written for this simulator. Other browsers might work - but I wouldn't count on it. ENJOY!
|
| « Last Edit: Jul 25th, 2004, 2:07pm by mattian » |
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
 |
Re: The ASYLUM
« Reply #1 on: Jul 25th, 2004, 6:37am » |
 Quote  Modify
|
Opera doesn't work, for instance.
::It is not possible to guarantee an escape. You can if you find the key in ward A. If not, you first move might loose information about where you were. If A and C lead to B via door 1, and your first move is 1, you will never know which of A and C was your starting position.
If you have the key in ward A, leave it there until you have figured how to go to the next room and back. Then you move the key one room and restart. When you have moved 4 times, you are in room E, whatever direction you took.
::
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: The ASYLUM
« Reply #2 on: Jul 25th, 2004, 6:40am » |
Quote Modify
|
PS: nice simulation, by the way. It reminds an old game where at some place you are in a twisty maze of passages, all alike.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: The ASYLUM
« Reply #3 on: Jul 25th, 2004, 9:09am » |
Quote Modify
|
Quote:| nice simulation, by the way. |
|
I will create a GUI for all the riddles I post from now on. Makes it more fun. So let me know if there are any riddle scenarios in this forum (or otherwise) that you want me to simulate.
|
| « Last Edit: Jul 25th, 2004, 3:04pm by mattian » |
IP Logged |
|
|
|
Three Hands
Uberpuzzler
Gender:
Posts: 715
|
|
Re: The ASYLUM
« Reply #4 on: Jul 26th, 2004, 11:17am » |
Quote Modify
|
It does look like you need a certain amount of luck to get out of the asylum...
Given that the key is the only "signpost" you get, and you can't tell which door you cam through when you move into another ward (clearly a good reason for you to be locked up in the first place - with that kind of short term memory  ). Therefore, probably you're best plan is to keep track of the route you took to find the key, and then effectively use the key to help map the entire asylum. This would probably take quite a lot of time, however. Having then worked out a map of the asylum, you can then, I would imagine, work out which room the key originated in, and so what route to take to get to Ward E - and thus freedom.
I imagine that counts as a bare bones for a solution, and just needs someone to crunch numbers to work out how long you would be expected to take. Or come up with a better solution, as I expect you'd be in there for quite a long time...
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: The ASYLUM
« Reply #5 on: Jul 26th, 2004, 11:38am » |
Quote Modify
|
Grimbal, Three hands:
Actually - as both of you have pointed out - there was an omission in the original puzzle which makes it ...
::
... impossible to guarantee success for the patient - unless the key is found in ward A. This was not my intention when it was constructed. It was an oversight on my side before publishing it. One option is to add a constraint that says, "The key is in ward A."
::
|
| « Last Edit: Jul 26th, 2004, 11:54am by mattian » |
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: The ASYLUM
« Reply #6 on: Jul 26th, 2004, 11:44am » |
Quote Modify
|
Three Hands:
I don't think it takes all that long (not all that short either - don't get me wrong), but barring the issue described by you and Grimbal, the solution is fairly simple - assuming the patient has a really good memory.
|
| « Last Edit: Jul 26th, 2004, 11:46am by mattian » |
IP Logged |
|
|
|
Three Hands
Uberpuzzler
Gender:
Posts: 715
|
|
Re: The ASYLUM
« Reply #7 on: Jul 27th, 2004, 7:39am » |
Quote Modify
|
True - if you find the key in Ward A,you only need to find out the way forward and back around half the wards. Given that in each room one does nothing, one goes forwards and one goes backwards, the method that seems to work best is to leave the key initially in Ward A, and go through a door. If you see a key on the floor, you can remember that door as the "same room". If you enter an empty ward, then you can assume you have gone forwards (Since direction does not matter particularly, as you only need to get 4 steps round). From this room, you then attempt to find a way back to room A by guessing a door. One door will cause you to stay put, one door will cause you to move away from A, but in either case, you can't tell. Therefore, there is a 1/3 (or 6/18 ) chance of guessing the way back immediately. If you switch doors after having chosen a door that leads you to a blank ward, you have a (1/3*1/2) = 1/6 (or 3/18 ) chance of finding your way back (Same room - back a room), ((1/3*1/2)+(1/3*1/3) = 5/18 chance of being two steps away (Same room - forward a room, Forward a room, same room), (1/3*1/3) = 1/9 (or 2/18 ) of being 1 step away (Forward a room, back a room), and 1/9 (or 2/18 ) of being 3 steps away (Forward - forward). However, by using that strategy, half the time you will findthe key again, and so know how to get from A to B, and B to A. So you then move the key to B and repeat. If you do not find your way back, then I imagine selecting doors at random until you find your way back to A is recommended, and if you manage to do this in less than 7 steps, you can guarantee that the last room you were in was B (since it takes 7 steps to get from B to A the long way round as a minimum, and you could not be certain that you did not manage to do that) and so know how to go A-B-A, so can continue. Otherwise, go back to room B and try a different door from the one you tried the previous time, with the odds slightly more in your favour this time. Having moved the key from A to B, know A-B-A, you can then repeat the same process of working out B-C-B, and then move to C, then D, and finally E, using the same principles. Previous results may be able to alter probabilities in rooms, but I'm not mathematical enough to know how to do that.
I'm not convinced, however, that it is entirely impossible to work out where you pick the key up if it is not in ward A to begin with. If you keep track o the route you took to get to the key, knowing that you started in A, then you have a route for how to get from A to ward 1 (the ward where you found the key). You can then work out the connections for the Asylum doors, using the mapping technique outlined above, only labelling your point of origin 1 instead of A. Then, knowing all the connections, you may be able to re-create the original journey you took, and so find out which ward for "your map" (1,2,3,4,5,6,7,8 ) corresponds to the "Asylum map" (A,B,C,D,E,F,G,H) Ward A, hence finding out the fastest route from your current ward to ward E, and escape. This process, however, I imagine would be expected to take a lot longer. For the initial part to work, however, I expect that a non-repeating pattern of doors being taken would need to be used, so as to avoid potential problems with not knowing when you started going through the "same" door for a ward, since that number door was also a door from an adjacent ward that took you into that ward - at least for the first couple of steps...
So, a possible method for success, but I'm not much good at crunching numbers...
[e] Sorry for adding more to what is already a long post...
After some time trying the method I suggested above for the original version in mattian's simulation (thank you for providing such a useful test-tool, btw  ) I've encountered a few occasions where I've been left with a 50:50 chance of guessing which ward is ward A (and hence ward E). This, I suspect, is mostly due to no finding an appropriate combination of doors to use while finding the key to avoid the situation where two wards could be your point of origin, if such a combination exists. I suppose now the challenge is two-fold: Find an optimal combination to use while moving from Ward A to the key, and then, having found the key, perfect the mapping of the ward doors in order to, as quickly as possible, determine which ward is ward A, and then move as quickly as possible to ward E.
For this latter challenge, I would guess that testing new doors as a possible "backtrack" of the combination you used to get from ward A to the key would be the optimal strategy in trying to do this as swiftly as possible. I would also add that I don't think I've used more than 100 steps to escape, although some attempts can get close to this, so my guess about taking a long time appears to be unfounded, when compared with those 100 prisoners in the complex across the street... [/e]
|
| « Last Edit: Jul 27th, 2004, 8:52am by Three Hands » |
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: The ASYLUM
« Reply #8 on: Jul 27th, 2004, 9:23am » |
Quote Modify
|
Quote:| If you do not find your way back, then I imagine selecting doors at random until you find your way back to A is recommended, and if you manage to do this in less than 7 steps, you can guarantee that the last room you were in was B |
|
Not true. It is possible your transition was A-B-C-D-D-C-B-A, for example. There are many other such examples which take you from A to A in seven steps.
Your probabilities approach is interesting, however, there is a more precise way to resolve the edges of the maze - which is also more efficient. Again - assuming you find the key in A.
Quote:| I'm not convinced, however, that it is entirely impossible to work out where you pick the key up if it is not in ward A to begin with. If you keep track o the route you took to get to the key, knowing that you started in A, then you have a route for how to get from A to ward 1 (the ward where you found the key). |
|
Finding the key from ward A a second time is easy - the trick is in finding ward A after you find the key. Consider the following example:
A1 - H (notation here is <current_ward><door> - <destination_ward>)
A2 - A
A3 - B
B1 - B
B2 - A
B3 - C
C contains the key
D1 - E
D2 - D
D3 - C
E1 - E
E2 - F
E3 - D
etc.
Now, consider the door sequence starting in A: (2, 3). Certainly, if you were given the opportunity to be transported back to A, you would be able to find the room with the key again. But finding A will need to be confirmed by the route used to arrive at C - in this case door 2 and then door 3. If you should stumble on ward E and use the sequence (2, 3), you would also end up at C, and draw the conclusion that E was A. Thus you would not be able to accurately differentiate between A and E.
Quote:| however, I expect that a non-repeating pattern of doors being taken would need to be used, so as to avoid potential problems with not knowing when you started going through the "same" door for a ward, since that number door was also a door from an adjacent ward that took you into that ward - at least for the first couple of steps... |
|
Absolutely - repeating sequences are definitely out - not only in the beginning - well spotted.
Quote:| I suppose now the challenge is two-fold: Find an optimal combination to use while moving from Ward A to the key, and then, having found the key, perfect the mapping of the ward doors in order to, as quickly as possible, determine which ward is ward A, and then move as quickly as possible to ward E. |
|
This is indeed a challenge - and will probably remain the solution to strive for. Whether an optimal sequence can be found - or even exists - will remain the subject of this thread, I think.
Quote:| I would also add that I don't think I've used more than 100 steps to escape, although some attempts can get close to this, so my guess about taking a long time appears to be unfounded, when compared with those 100 prisoners in the complex across the street... |
|
Yep - not too long.
Three Hands - are you still using your "probabilities" approach? If so, I still maintain that there is a more elegant mapping method - however, I do think probability can be put to good use in helping to decide which door to try at any given node, although only in cases where this information is not already available inherently within the mapping method.
|
| « Last Edit: Jul 27th, 2004, 9:34am by mattian » |
IP Logged |
|
|
|
Three Hands
Uberpuzzler
Gender:
Posts: 715
|
|
Re: The ASYLUM
« Reply #9 on: Jul 27th, 2004, 10:15am » |
Quote Modify
|
on Jul 27th, 2004, 9:23am, mattian wrote:
Not true. It is possible your transition was A-B-C-D-D-C-B-A, for example. There are many other such examples which take you from A to A in seven steps. |
|
For this, it was along the lines of "if you get back to A within 7 steps, then you know you cannot have got back to A via H, if you started A-B". This is just an observation so that you can map the connection from A to B with certainty as the last door you passed through, since from B it would be 7 steps to go the long way round to A (B-C-D-E-F-G-H-A). However, without further information, if you took 7 steps from B to get to A, you could not be certain whether you went B-C-D-E-D-C-B-A or B-C-D-E-F-G-H-A, or some other version. However, if you only take 6 steps, you know that the last step must have been B-A.
on Jul 27th, 2004, 9:23am, mattian wrote:
Finding the key from ward A a second time is easy - the trick is in finding ward A after you find the key. Consider the following example:
A1 - H (notation here is <current_ward><door> - <destination_ward>)
A2 - A
A3 - B
B1 - B
B2 - A
B3 - C
C contains the key
D1 - E
D2 - D
D3 - C
E1 - E
E2 - F
E3 - D
etc.
Now, consider the door sequence starting in A: (2, 3). Certainly, if you were given the opportunity to be transported back to A, you would be able to find the room with the key again. But finding A will need to be confirmed by the route used to arrive at C - in this case door 2 and then door 3. If you should stumble on ward E and use the sequence (2, 3), you would also end up at C, and draw the conclusion that E was A. Thus you would not be able to accurately differentiate between A and E. |
|
Indeed - This is where a lot of the difficulties in mapping back the trail from key to A come in - another variant on this would be:
A1: H
A2: A
A3: B
H1: H
H2: A
H3: G
With the starting combination (1,2), you would not be able to tell later if you started in A or H - a potential problem for complete solutions, so I think this puzzle will be more a case of maximising probability of escape 
on Jul 27th, 2004, 9:23am, mattian wrote:
Absolutely - repeating sequences are definitely out - not only in the beginning - well spotted. |
|
on Jul 27th, 2004, 9:23am, mattian wrote:
This is indeed a challenge - and will probably remain the solution to strive for. Whether an optimal sequence can be found - or even exists - will remain the subject of this thread, I think. |
|
Indeed - but as I stated above, I reckon it will come down to more of a problem of "maximising probability", rather than guaranteeing
on Jul 27th, 2004, 9:23am, mattian wrote:
Three Hands - are you still using your "probabilities" approach? If so, I still maintain that there is a more elegant mapping method - however, I do think probability can be put to good use in helping to decide which door to try at any given node, although only in cases where this information is not already available inherently within the mapping method. |
|
I've been approaching the puzzle with using a chart to map the Asylum having found the key based in the initial location of the key. Essentially, the probabilities are more looking at time expected for a successful map, as each time you move away from the key, you can only keep track of which doors you're going through, and also how many steps it takes you to get back to the key. If you get back immediately, then the connection between rooms is simple. If it takes two steps to get back, then you must have gone Same-Back, and so you get a full map of the room you were just in. If it takes 3 steps, then you must have gone Forward-Back-Back (assuming you do not go through the same door for the first two steps, otherwise it could be Same-Same-Back), so you get even more information (including the full map of the first room you went to from the key), but beyond that, it becomes impossible to tell (I think). However, using what information I can from this chart, it becomes simpler to navigate - the tricky part being retracing steps for Ward A. So it could potentially take quite a long time to do all of this (at least with my level of detail while mapping), but, as I said, I think I'd be out of the Asylum before those 100 prisoners with one lightbulb get away...
Just out of interest, what method have you been using for mapping the Asylum, mattian?
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: The ASYLUM
« Reply #10 on: Jul 27th, 2004, 11:04am » |
Quote Modify
|
Quote:| ... seven steps or less ... |
|
I understand what you mean now - quite right - sorry.
Quote:
so I think this puzzle will be more a case of maximising probability of escape
|
|
Right - which is an interesting objective. But it will be a function of the position of the key and the number of transitions used to find it. The range will be anything from 100% likely (in cases where the key is found unambiguously) down to whatever maximum minimum we can find.
Quote:| Just out of interest, what method have you been using for mapping the Asylum, mattian? |
|
Well it's hardly kosher for the author of a puzzle to relinquish his solution too early in the game, but I will post it here anyway - since Wu's site isn't seeing much traffic at the moment. Also - it looks as though it might be more interesting to investigate those probabilities as a team since I haven't solved that aspect of the puzzle myself - yet.
::
Let's consider the case in which the key is found in the first room - ward A.
STEP 1
======
Choose a door and write down the location and the door choice.
Example: A1
If you find the key again then you know the following edges:
A1:A
A2:B
A3:H
The choice of B and H in this initial case is completely arbitrary. So for convenience it is best to choose B according to the next door chosen.
Now consider the case in which you do not find the key; It means that you transitioned to ward B - again, it may be ward H, but it doesn't matter. In this initial step - it's arbitrary, as long as all decisions following this one conform to this chosen convention.
Okay... In this case, you know then the following edges:
A1:B
A2:A|H
A3:H|A
STEP 2
======
From ward B you now choose a door - Example: B2
Write down the possible transitions that have taken place:
a) A1:B2:A
b) A1:B2:B
c) A1:B2:C
The possible outcomes are: a) you find a key, or b) you don't find a key.
If you find a key then (a) is the only possible transition sequence and (b) and (c) are eliminated. And you have among your known edges the bi-directional edge: A1:B and B2:A - move the key to B.
If you don't find a key then (a) can be eliminated and BOTH (b) and (c) survive.
STEP 3
======
From ward B or C (you don't know which yet), choose a door - Example: [B|C]3
Possible transitions:
a) A1:B2:B3:A
b) A1:B2:B3:B
c) A1:B2:B3:C
d) A1:B2:C3:B
e) A1:B2:C3:C
f) A1:B2:C3:D
Two outcomes - key or no key.
key: Eliminate (b), (c), (d), (e), (f)
no key: Eliminate (a) and (b) - (b) is eliminated because it claims that B2 and B3 lead to B which is a contradiction.
STEP 4
======
Choose a door to establish the grounds for a contradiction to eliminate potential transition maps.
In this case door 1 is a good choice because it adds a second B entry to (d) which narrows the options down there - essentially we're challenging the paths we have to turn up the key - if it does, we learn something, if it doesn't, we also learn something.
So
a) A1:B2:B3:C1:B
b) A1:B2:B3:C1:C
c) A1:B2:B3:C1:D
d) A1:B2:C3:B1:A
e) A1:B2:C3:B1:B
f) A1:B2:C3:B1:C
g) A1:B2:C3:C1:B
h) A1:B2:C3:C1:C
i) A1:B2:C3:C1:D
j) A1:B2:C3:D1:C
k) A1:B2:C3:D1:D
l) A1:B2:C3:D1:E
key: Eliminate everything except (d).
no key: Eliminate (f) contradiction {B2:C, B1:C}, (h) contradiction, etc.
ETC.
===
This list will grow long and deep - but it's easy to maintain. When the key is found - the path (or potential set of paths) will remain after the others are all eliminated. The unique solution can be failure testing using the key as a marker which verifies or rejects potential solutions based on whether the key is found according to expectation. When the key is found after a long dry spell, many of the transitions will already be known - via the known set of paths that satisfy the sequence.
In the case where the key is not in the first room:
If the key is in the second room and found in the first move - it is essentially the same as finding it in the first room. If the key is in the third room and found after two transitions, then - again - the same solution can be used.
Simply put: If the key is found within the first two transitions, there is no issue.
If the key is not found within the first two transitions, then the same principle may be used, but it may easily result in multiple solutions. Suppose, for argument's sake that three of a potential four solutions indicate that a particular ward X is ward A while the fourth solution shows that ward Y is ward A - clearly there is a 75% chance that ward X is ward A.
::
|
| « Last Edit: Jul 27th, 2004, 11:18am by mattian » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
   
Gender:
Posts: 2873
|
|
Re: The ASYLUM
« Reply #11 on: Jul 28th, 2004, 5:57am » |
Quote Modify
|
It looks like, for a given key-finding strategy, it's always possible to design a set of links so that you can only narrow down your start point to one of seven rooms. Certainly it's possible to come up with scenarios where no search pattern can distinguish between three rooms you could have started in...
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: The ASYLUM
« Reply #12 on: Jul 28th, 2004, 6:10am » |
Quote Modify
|
Yes - if you were to apply an additional constraint, for example, which says:
If door d in ward x leads to ward y, then all other doors leading to ward y are NOT door d.
Then it would be possible to unambiguously find any ward by backtracking along the transition path.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: The ASYLUM
« Reply #13 on: Jul 28th, 2004, 6:14am » |
Quote Modify
|
Oh! By designing a set of links, you mean as the patient solving the problem, and not the architect of the Asylum.
I can't see how such a strategy might be chosen; without some additional information.
|
|
IP Logged |
|
|
|
Three Hands
Uberpuzzler
Gender:
Posts: 715
|
|
Re: The ASYLUM
« Reply #14 on: Jul 28th, 2004, 9:43am » |
Quote Modify
|
Mattian, I think the search pattern you described (having found the key) is more or less what I have been using (just less well explained) - although I'll confess not in the same level of detail, since I've been somewhat lazy about keeping notes... . However, I would propose that, if working on the premise that the key was not found in ward A, it may be simpler to label the wards while mapping from where you find the key with different terms - I think rmsgrey's suggestion (when we were discussing this offline) of labelling the ward where you find the key K, and the other wards L,M,N,O,P,Q and R - similar to the alphabetical labelling of the wards previously, is the most suitable I can think of.
One other interesting point from the probabilities - after finding the key, and so labelling the ward you find it in K, you also know which door that either L or R (depending on subsequent labelling) connects to K from. This then means that for the start of your maping, having left K, you have a 2/3 chance of returning to K through the door which you first went through to get to K. For instance, if, after some moderate searching, you go through door 1 in ward x (unknown ward), and find the key. After beginning your map with the room you just enter as K, after leaving K, trying door 1 has a 1/3 chance of success from one direction, but is guaranteed to be successful in the other - you just don't know which is which. Say that you actually came to K from L through door 1: The possibilities are therefore (after leaving K)
Go to R:
1 = K/R/Q
2 = K/R/Q
3 = K/R/Q - 1/3 chance for each
Go to L:
1 = K
2 = L/M
3 = L/M
So going through door 1 guarantees returning to K in one direction, and has a 1/3 chance of working in the other, and so has a 2/3 chance overall of returning you to K, while doors 2 and 3 have a 1/6 chance. This kind of probabalistic method could possibly be expanded for further optimising a mapping technique (possibly to justify more clearly what I say below), but I'll leave that for some other time, when I'm thinking more mathematically.
In terms of trying to ensure accurately back-tracking to A, and so being able to find ward E after finding the key, I also think that, when mapping from room L (arbitrary label for <room entered after K found>) and onwards, attempting the door you tried in the sequence prior to succeeding in finding the key. To expand on the example above, the sequence in finding the key finished (2,1). Knowing that the connection from L to K is through L1, trying L2 should tell you one of two things - either L2 leads to L - causing a repeat motion in your search, that L3 goes to M, and that either door 2 or whichever door preceded it in your search for K leads from M to L (assuming you're not unlucky enough to get a false trail through both L1 and R1 going to K) - or L2 leads to M - implying either M2 returns you to L, or you're going the wrong way round the asylum to back-track to A along the route you came. In either case, it seems to me to be a useful method for recreating your journey though the asylum from A to K
I hope this is clear enough - as you may have guessed, ideas I have do not always get translated clearly from brain to text...
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: The ASYLUM
« Reply #15 on: Jul 28th, 2004, 10:31am » |
Quote Modify
|
The reason I thought my solution differed from yours is because yours seemed to get more and more complex with each transition while mine became more volumous. In other words - your descriptions of probabilities at each ward became something like, for example: w * (x * (y * (z)))), where dependencies were described in terms of previous dependencies.
I saw this as an unnecessarily complex description of the solution. In my solution - when the key is found for the second time, all but two or three transition paths are eliminated (by contradiction) and only the very specific possibilities remain. It is not concerned with why things happened the way they did - only that they did happen the way they did. The interesting thing here is that finding the key (representing a single bit) after a long set of unfruitful transitions gives us a large amount of information all at once. I think of it in the same context as the red-eyed/brown-eyed monk riddle in the medium section of Wu's riddles - for n monks, there is no conclusive information for (n-1) days, and then all the information is confirmed on the nth day.
Essentially, I think your initial solution description was proposed as a relative interpretation of each transition while mine is absolute. As you say, they may very well boil down to the same thing, but I wonder how easily your approach can be maintained for large numbers of transitions.
Quote:| ...it may be simpler to label the wards while mapping from where you find the key with different terms... |
|
Right - I did the same thing.
Quote:| ...having left K, you have a 2/3 chance of returning to K through the door which you first went through to get to K. |
|
Nice. That's what I was suggesting earlier when I said that probabilities could help in deciding which door to choose in any given ward. And I agree - I think there is potential to take it further in the complete solution - principally in the final decision as to which ward is the true ward E.
|
| « Last Edit: Jul 28th, 2004, 10:34am by mattian » |
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: The ASYLUM
« Reply #16 on: Jul 29th, 2004, 9:09am » |
Quote Modify
|
This puzzle reminded me of a problem concerning a sequence of ternary digits with no consecutive repetitions of any length Sloane's A085794, It seems that this sequence guarantees the lowest average number of moves before finding the key because it escapes out of any loop.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: The ASYLUM
« Reply #17 on: Jul 29th, 2004, 10:46am » |
Quote Modify
|
NICE! I was trying to find a good sequence on my own. I thought there might already exist such a sequence - but didn't know how to find it.
What is the guaranteed number of moves then to find the key? i.e. Worst case scenario?
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: The ASYLUM
« Reply #18 on: Jul 29th, 2004, 11:13am » |
Quote Modify
|
The portion of the sequence that Leonid posted, will not reach rooms D, E, F or G in the worst case: Here is a test sequence:
A0, A1, B0, A2, H0, A1, B2, B0, A2, H1, H0, A1, B2, B0, A1, B0, A2, H0, A1, B2, B0, A2, H1, H0, A2, H0, A1, B0, A2, H1, H0, A1, B2, B0, A1, B0, A2, H0, A1, B2, B0, A2, H1, H0, A1, B2, B0, A1, B0, A2, H1, H0, A1, B2, B0, A2, H1, H0, A2, H0, A1, B0, A2, H1, H0, A1, B2, B0, A1, B0, A2, H0, A1, B2, B0, A2, H1, H0, A1, B2, B1, C0, B2, B0, A1, B0, A2, H1, H0, A1, B2, B0, A1, B0, A2, H0, A1, B2, H0, A2, H1, H0, A2, H0, A1
That's 105 steps to cover four rooms in the worst case (in the worst case I could find, anyway).
Surely the best sequence will depend on the number of nodes in the network. In other words - is this sequence not constructed as a function of the number of nodes to which it relates?
For example: Take the case of two wards - a sequence to escape all loops would be something like: 0, 1
Three wards: 0, 1, 0, 1, 2, 1
I don't know what I'm getting at here, but it seems as though a temporally unique sequence has a pattern to it which specifically repeats with minor changes. The frequency of this very slightly varying pattern should have some relationship to the number of wards that need to be covered by the sequence.
P.S. If anyone knows what I'm talking about, please explain it to me.
|
| « Last Edit: Jul 29th, 2004, 7:26pm by mattian » |
IP Logged |
|
|
|
Three Hands
Uberpuzzler
Gender:
Posts: 715
|
|
Re: The ASYLUM
« Reply #19 on: Jul 30th, 2004, 7:46am » |
Quote Modify
|
I think I understand the problem you're looking at, but I don't think I can provide any answers for it.
Basically, for the given path, you want to be able to guarantee that you enter all 8 wards at some point, but without using a repeating pattern to search with. This way, you're guaranteed to find the key at some stage during the search, and also have the best chance of being able to determine where Ward E is after finding the key.
In order to guarantee that you have gone in each direction, though, my first guess is that you need to be certain that for each ward, at some point on the pattern you would, assuming worst case, have passed through all three doors. Because of this, the more wards you have already been into, the harder it is to guarantee that for either of the wards at the edge of your search you will at a given point, have passed through all three doors. As you have shown, for one, to and three wards, it is fairly simple, but four wards looks to be more tricky (although guaranteed using the pattern suggested by Leonid), and five, six, seven and eight wards will probably become even more difficult to work out.
So finding an optimal pattern for the search for the key looks like it's going to be harder than I' originally suspected 
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: The ASYLUM
« Reply #20 on: Jul 30th, 2004, 8:00am » |
Quote Modify
|
I'm sure the sequence to which Leonid referred, will work, however, I don't know how to continue it. I did manage to spot some patterns within patterns within the partial-sequence, but nothing that would suggest how to continue it - unless we simply verify with each new sequence element - using brute force - that time-shift uniqueness remains in effect.
Also - I don't know at this point if we're even looking for the optimal sequence - I would be happy to find a sequence that simply guarantees a visit to all eight wards. I think I have an idea though - using the same method used in my posted solution, I could map out all possible outcomes and eliminate redundancy - ultimately, despite my efforts to keep the visited wards to a minimum, the sequence should force all outcomes into the all-wards-visited state. I'll give that a go.
... time passes ...
hmmm - I wonder if that will work.
Anyway, with a worst case for finding the key, I believe we could calculate the probabilty of finding the true Ward E in the worst case.
|
|
IP Logged |
|
|
|
asterix
Guest
|
That really doesn't seem to be the best sequence for what we're trying to do. The problem is that it tries so hard to avoid any pattern at all, when, in fact, sometimes you will want some pattern. Suppose three rooms in a row have the same door combinations. The sequence never lets you go through a door twice in a row (at least in the first hundred steps that are listed), so to pass through all three you would need a sequence like A1B0B1C0C1D. Will this sequence ever have a 10101 subsequence? Judging from the beginning of the sequence, it would seem that any subsequence of four steps always contains all 3 digits (0,1,2).
|
|
IP Logged |
|
|
|
asterix
Guest
|
Let me amend that. It will get through eventually taking some backsteps along the way. But in mattian's worst case scenario where you've taken 105 steps and you're still in room A, an optimized set of steps would recognize that as soon as you've taken 7 steps and not found the key some door combinations are ruled out. Long before you get to 105, it should be possible, somehow, to realize you're just going back and forth, and by ruling out the all the combinations that would have carried you around the whole asylum, get you out of the loop a lot faster than the sequence will
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: The ASYLUM
« Reply #24 on: Jul 30th, 2004, 4:25pm » |
Quote Modify
|
on Jul 30th, 2004, 1:09pm, asterix wrote:| Will this sequence ever have a 10101 subsequence? Judging from the beginning of the sequence, it would seem that any subsequence of four steps always contains all 3 digits (0,1,2). |
|
By definition, no subsequence of any length appears twice in a row, therefore any 4 steps always contain all 3 digits.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove