Skip to main content

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

One important observation is that:

The way out is behind thean odd-numbered hallway.

This is because:

Each dead-end room connects two adjacent hallways. So boththe set of all doors to the west side and east side of way outthe exit have even numbers of hallways. Thus, the way out is behind thean 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

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

One important observation is that:

The way out is behind the odd-numbered hallway.

This is because:

Each dead-end room connects two adjacent hallways. So both the west side and east side of way out have even numbers of hallways. Thus, the way out is behind the 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

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

add visual help
Source Link
athin
  • 34.3k
  • 4
  • 72
  • 224

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

One important observation is that:

The way out is behind the odd-numbered hallway.

This is because:

Each dead-end room connects two adjacent hallways. So both the west side and east side of way out have even numbers of hallways. Thus, the way out is behind the 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

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

One important observation is that:

The way out is behind the odd-numbered hallway.

This is because:

Each dead-end room connects two adjacent hallways. So both the west side and east side of way out have even numbers of hallways. Thus, the way out is behind the 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!

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

One important observation is that:

The way out is behind the odd-numbered hallway.

This is because:

Each dead-end room connects two adjacent hallways. So both the west side and east side of way out have even numbers of hallways. Thus, the way out is behind the 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

Source Link
athin
  • 34.3k
  • 4
  • 72
  • 224

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

One important observation is that:

The way out is behind the odd-numbered hallway.

This is because:

Each dead-end room connects two adjacent hallways. So both the west side and east side of way out have even numbers of hallways. Thus, the way out is behind the 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!