49
$\begingroup$

Once again, you have angered the Emperor, and she has imprisoned you in a special prison.

“I do have a bit of good news for you,” the Emperor has told you. “You're only two doors away from freedom, and I've left all the doors unlocked for you!” Of course, she neglected to mention the details.

So here are the details. From the main part of your prison suite, you can walk into a very long hallway. The hallway runs east and west, and on the north side of the hallway, there are 2,001 doors. (Evidently, the Emperor really, really likes doors.) Each door leads into another very long hallway, running north and south. The north–south hallways are so long that it takes about half an hour to walk from one end to the other. At the north end of each of these hallways is another door.

At the north end of one of these hallways, the door leads to freedom. At the north end of each of the other hallways, though, the door simply leads to a dead-end room. The dead-end room has two doors, both on the south side. One door leads to the hallway you just came from (obviously), and the other door leads to the adjacent hallway.

You have access to some simple supplies: pencils, paper, sticky tape, scissors, and plenty of string. (Of course, you probably won't need all of them. Maybe you won't need any of them.)

How are you going to get out? If you try doors at random, it could take you hundreds of hours to find the right one.

Ah, but you've just thought of something. You've figured out a way to escape from the prison in under a week, guaranteed.

What is it?

$\endgroup$
  • 1
    $\begingroup$ Hey ! I have a question : did you already ask this puzzle with a picture/diagram/visual help ? If yes, did it help them ? Like they found quickier than without ? Other question : why 2001 ? :D $\endgroup$ – Neyt May 28 at 9:53
  • 1
    $\begingroup$ You should probably specify a bit on the N/S hallways, and explicitly make them all the exact same length (instead of "about half an hour to walk"). Because I was stymied with the thought: what if the escape hallway was 20 feet shorter than the rest and had a ladder leading upward to freedom. Which makes solving the problem optimally pretty much impossible. $\endgroup$ – Kevin May 28 at 15:06
  • 3
    $\begingroup$ @Neyt Nope, I haven't posed this puzzle to anyone before. The number is 2,001 because that's a number that works :) $\endgroup$ – Tanner Swett May 28 at 15:53
  • 1
    $\begingroup$ @Kevin Hmmmm, I don't quite understand your scenario and how it makes the problem more difficult. Maybe you could explain it in more detail in a chat room? $\endgroup$ – Tanner Swett May 28 at 15:55
  • 1
    $\begingroup$ Not sure how to open a chat room (or if I have the reputation for it.) I'll just put it this way: what happens when corridors #X and #X+2 connect to a room at the long end of the hallway, and corridor #X+1 stops short of reaching that room - instead, ending with a ladder that leads to freedom. The corridor lengths need to be defined explicitly equal instead of with "eh, about ABC long" to prevent that possibility. $\endgroup$ – Kevin May 29 at 13:08
40
$\begingroup$

Let's number the hallways (doors) from $1$ to $2001$ from west to east.

One important observation is that:

The way out is behind an odd-numbered hallway.

This is because:

Each dead-end room connects two adjacent hallways. So the set of all doors to the west and east of the exit have even numbers of hallways. Thus, the way out is behind an odd-numbered hallway.

Now, another important observation is that, if a dead-end room connects hallway $i$ and $i+1$:

If they are on the west side of the way out, then $i$ must be odd (and $i+1$ must be even.) This is because the connections are $(1,2),(3,4),(5,6),\cdots$. Conversely, if they are on the east side of the way out, then $i$ must be even (and $i+1$ must be odd.) This is because the connections are $\cdots,(1996,1997),(1998,1999),(2000,2001)$.

Combining both observations:

We can do a binary search! Let's pick an odd-numbered hallway as middle as possible from the solution candidates e.g. $x$. If it's a way-out, you're lucky! If it connects to an even-numbered hallway which is lesser than it a.k.a the other hallway is on its west ($x-1$ is even and $x$ is odd) then we are on the east side of the way out. Thus, the way-out hallway must be $<x$. Conversely, If it connects to an even-numbered hallway which is greater than it a.k.a the other hallway is on its east ($x$ is odd and $x+1$ is even) then we are on the west side of the way out. Thus, the way-out hallway must be $>x$.

How long will it take for us to survive?

It's roughly $log_2$ factor so at most $10$ or $11$ trials perhaps. The exact hour is not important but it takes less than a day to survive!

This is a visual help:

enter image description here

| improve this answer | |
$\endgroup$
  • 6
    $\begingroup$ Actually, each failed attempt removes 2 doors and divides the rest in 2, rounded to the nearest odd number. The number of possible doors goes like this: 2001 -> 999 -> 499 -> 249 -> 123 -> 61 -> 29 -> 13 -> 5 -> 1. So, in the worst case, you have 9 failed attemps. The 10th attempt is guaranteed to lead you to freedom. You are free in 9.5 hours or less. PS: plus maybe half an hour to walk between the doors between attemps. $\endgroup$ – Florian F May 27 at 7:22
  • 2
    $\begingroup$ @FlorianF you need to add the time spent walking east and west. $\endgroup$ – msh210 May 27 at 7:24
  • 2
    $\begingroup$ @musefan doesn't matter as long as you remembered which hallway you are on right now. $\endgroup$ – athin May 27 at 13:24
  • 5
    $\begingroup$ @athin: Doesn't matter?? My brain disagrees. I would probably lean towards the other path as I would feel bad the one path got visited twice and the other didn't get any visits. I wouldn't want the odd path to make fun of the even path for never getting used. Perhaps I am overthinking it... $\endgroup$ – musefan May 27 at 13:49
  • 14
    $\begingroup$ You should return via the other path, because what if you find a nickel on the floor? $\endgroup$ – Tanner Swett May 27 at 14:50
10
$\begingroup$

As an easy-to-remember simple implementation of @athin's excellent answer:

Starting before the first door, and until you walk out the exit

Skip 1000 doors to reach door #1001, enter it, and follow the other door out. Whatever side you came out of, continue in that direction (e.g., if the door was on the west side (e.g. 1001->1000) continue to the west when you exit).

After each exit,

Skip half the number of doors you skipped last time, rounded to the nearest odd (down for ties) since you will always be exiting an even door: 1000 -> 499 -> 249 -> ...

As mentioned by @FlorianF, this

Is guaranteed to get you out in at most 9.5 hours (plus ~2000 door-separations of walking, which is probably 20-30 minutes).

With an expected time (assuming random positioning and ignoring E-W movement) of

.5 + (0/1001 + 1000/1001 * (1/500 + 499/500 * (2/250 + 249/250 * (3/125 + 124/125 * (4/62 + 61/62 * (5/31 + 30/31 * (6/15 + 14/15 * (7/7 + 6/7 * (8/3 + 2/3 * (9/1)))))))))) ~= 8.507 hours

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Good one! Sometimes it is not easy to find this kind of practical implementations of algorithm $\endgroup$ – justhalf May 29 at 9:24
6
$\begingroup$

I am thinking this through as I type.

Where I would start, and the theory I proceed under:

I start at the west end. As there's no door to the west of that door, it must either connect to the exit or the door to the east. I spend an hour verifying it's not the exit, and now I know that door 1->2, and so 3->4... and so on until the unpaired exit hallway, so my theory is that I will find an odd door that connects to a door to the west, and then I will know that the exit is west of that door.

How I move forward from there:

I can cut the 1,999 remaining doors in half by walking down to door 999. Use the tape to mark every 10th odd door to make them easier to count, and use the pencil to note the actual number on them if possible, but counting taped doors would work.

Narrowing it down:

If 999 connects west, then I know my exit is < 999, east > 999. Second door is then halfway again (499 or 1499) and so on.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ You don't need to check the west door first - you can skip to the next phase immediately. $\endgroup$ – user2357112 supports Monica May 28 at 22:02
0
$\begingroup$

OK, lets look at the problem first.

I think we can...

turn the problem into a binary search!

To do this we first have to notice a few things about the problem. Each dead end room has two doors exiting it. One to the corridor that you came from and one to the adjacent corridor.

From this property we can apply this logic...

If we number the doors from 1 to 2001 (from west to east) then we notice that at the start of the corridor the doors 1-2, 3-4, 5-6, and so on will share a room. Always with the odd numbered corridor to the west and the even numbered corridor to the east. At the end of the corridor the doors 1996-1997, 1998-1999, 2000-2001 will share a room always with the even numbered corridor to the west and the odd numbered corridor to the east. This is because at some point along the main corridor our escape route takes up one of the numbers on its own. This means that the next corridor shifts the parity along by one. We’ll call this property the “parity” of the dead end room. Odd parity is with the odd number on the west. Even parity is with the even number on the west.

Further to this we know that...

...the escape route must be an odd numbered door. Otherwise we would have to have a dead end room to the west of the escape that only has a single door back out of it. i.e. there must be an even number of corridors to the west and east of the escape.

So, we can perform our search by using the following "algorithm"...

Starting with the range 1-2001 pick an odd number half way along the range. (1001 in this case). Now enter the corridor and walk to the end. If the door is the escape we’re done. If not note which way the doors are arranged in the dead end room. If you enter on the east of the room then the escape route is a higher numbered corridor than the one you’re in. (And vice versa). So adjust the range up (for odd) or down (for even) based on the parity of the dead end room. 1-1000 for even and 1002-2001 for odd. Now repeats the steps using the new range. If needed you may keep a not of the current range on your piece of paper but two numbers is not hard to remember :D

Performance of this escape...

This is a binary search (which I first thought we could use) and so has speed of log(n) which is about 11 (where n = 2001). So the length of time for this search would be 11 hours. 1 hour (to walk to the north end of each chosen corridor and back) * 11 (the number of corridors you would have to search).

So we can definitely escape in less than a week. It just takes half a day of lots of walking.

| improve this answer | |
$\endgroup$
0
$\begingroup$

You can improve @athin solution by knocking on the East or West walls once in the small room. Depending on what you hear you can deduce whether you're next to the exit, or 2 additional wrong rooms, thus improving the algorithm. I'm sorry I cannot comment on their answer.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Can you clarify how this would make a difference? I'm not sure how you would tell the difference between a wall between two rooms and a wall between a room and a corridor... $\endgroup$ – Chris May 29 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.