It seems to me that this epic voyage was actually:
Having arrived at the start, I was ready to start my journey. I found a vessel, and began.
To start, I let myself drift west as far as I could, which, looking left, allowed a nice view back at where I arrived. Finally I could drift no further and turned north before continuing.
I found myself surrounded, ...
The basic principle, as with other problems of this type, is that we start with two sets.
We want to count the size of the prison population - a set $P$ with $n$ members.
We start with two known subsets:
$S_0$ consisting of exactly 1 person who is writing the plans.
$P \setminus S_0$ everyone not in $S_0$
The initial goal is to partition $P$ into $k$ ...
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.
OK, lets look at the problem first.
I think we can...
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...
Further to this we know that...
So, we can perform our search by using ...
As an easy-to-remember simple implementation of @athin's excellent answer:
Starting before the first door, and until you walk out the exit
After each exit,
As mentioned by @FlorianF, this
With an expected time (assuming random positioning and ignoring E-W movement) of
Let's number the hallways (doors) from $1$ to $2001$ from west to east.
One important observation is that:
This is because:
Now, another important observation is that, if a dead-end room connects hallway $i$ and $i+1$:
Combining both observations:
How long will it take for us to survive?
This is a visual help: