Proving that a solution to the "Cat behind 7 doors" puzzle is optimal

Question

The "Cat behind 7 Doors" Puzzle.

There are 7 doors on a corridor, and a cat is behind one of them. We are trying to find the cat. Interesting thing is that, whenever the door we open is empty, we must close it after, and the cat must move to the door adjacent to him (1 right or 1 left). The cat can move to the door we have just closed.

I was able to find that the solution for the number of trials for $n$ number of doors (when $n$ is larger than 3) is $2(n-2)$. And the order in which we do the trials is starting with 2nd door and going one by one until the $(n-1)$th door, repeating $(n-1)$ and going back to the 2nd door. For example for $5$ doors, the trials are $2$, $3$, $4$, $4$, $3$, $2$.

I understand why this solution is correct. However, I am having a hard time proving if/why this solution is optimal, and I'm not even sure how to make a start on it. Do I use proof by induction? Do I use the formula? Any answers/help will be very much appreciated!

Answer 1

We need to go through everything and see where it leads us, I will try to use as little mathematical notation as I possibly can get away with. Describing these problems with words are more fun in my opinion.

First off we realize that the cat always moves from an odd numbered door to an even numbered door or vice versa.

So let's assume that the cat starts off in an even numbered door, i.e. any of the doors {$2$ or $4$ or $6$}.

1. Check door $2$, if the cat is there you win, else it was in {$4$ or $6$} and will move to {$3$ or $5$ or $7$}
2. Check door $3$, if the cat is there you win, else it was in {$5$ or $7$} and will move to {$4$ or $6$}
3. Check door $4$, if the cat is there you win, else it was in door $6$ and will move to {$5$ or $7$}
4. Check door $5$, if the cat is there you win, else it was in door $7$ and will move to $6$
5. Check door $6$, find the cat

So these steps will always work IF the cat started off in an even numbered door. Let's go through everything again and see what happens if it actually started off in an odd numbered door instead, i.e. door {$1$ or $3$ or $5$ or $7$}:

1. We checked door $2$, we didn't find it. The cat move from {$1$ or $3$ or $5$ or $7$} to {$2$ or $4$ or $6$}
2. We checked door $3$, we didn't find it. The cat move from {$2$ or $4$ or $6$} to {$1$ or $3$ or $5$ or $7$}
3. We checked door $4$, we didn't find it. The cat move from {$1$ or $3$ or $5$ or $7$} to {$2$ or $4$ or $6$}
4. We checked door $5$, we didn't find it. The cat move from {$2$ or $4$ or $6$} to {$1$ or $3$ or $5$ or $7$}
5. We checked door $6$, we didn't find it. The cat move from {$1$ or $3$ or $5$ or $7$} to {$2$ or $4$ or $6$}

If the cat starts off in an odd numbered door, after we've done the first round, the cat will just be in an even numbered door! This means we can just go back to the first round, and that second time we are guaranteed to find the cat.

So compiling this information for an odd number of doors:

Start with door $2$, increment with $1$ until you reach door $n-1$. If the cat started off in an even numbered door, you will have found it by now; else it started off in an odd numbered door and you just have to repeat the process one more time, which will make you find it.

This will indeed give a worst-case scenario of $\mathcal{O}(n)$, that is if you have to check all doors from $2 \Rightarrow (n-1)$ twice, which is $n-2$ doors twice, which is $2(n-2)$ or $\mathcal{O}(n)$.

Also notice that when we go through the first round, we always pick the door that will minimize the number of doors that the cat can move to; giving the cat as few doors as possible that it can move to. This will yield us the optimal solution.

Answer 2

We number the doors by $1,2,3,...,n$. Our method is, basically, check the following sequence of doors in each iteration and we want to prove this guarantees to find the cat no matter how the cat move. $$2,3,4,...,n-1,n-1,n-2,...,2$$

We prove the correctness of the method by using function property. We first show that if the cat starts in an even numbered door, we are guaranteed to find it during the first half of the traversal.

We let the number of iterations passed be our $x$ axis and the position of us be $f(x)$, the position of the cat be $g(x)$. The position is defined as the door number.

For example, using our traversal method, $$f(1)=2, f(2)=3, f(3)=4,..,f(n-2)=n-1$$

And $g(x)$ can be anything satisfying the following condition: $|g(x+1)-g(x)|=1$ for all $x$

Here comes the trick: note that they are discrete functions but we can approximate them with continuous functions. We extend $f(x)$ so that $f(x)=x+1$ for all real numbers $x$. We also extend $g(x)$ so that we keep the integer points and connect adjacent points with straight lines.

Notice the fact that $|g(x+1)-g(x)|=1$ for any integer $x$.

Now, since the cat starts in an even position, the following must be true.

(1)It cannot start at position $1$ and,

(2)After the $(n-2)$th iteration it cannot end at position $n$, because after $n-2$ iterations the cat has moved $n-3$ times (the first iteration the cat does not move). If $n$ is even $n-1$ is odd and the cat must end at odd position and if $n$ is odd similarly.

Now, we can conclude that $g(1)>=2$ and $g(n-2) <= n-1$

because we have extended $f(x)$ and $g(x)$ to continuous functions on real numbers in interval $[1,n-2]$, we can define $h(x)=f(x)-g(x)$ be another continuous function.

Note that $$h(1) = f(1) - g(1) >= 2 - 2 = 0$$ and $$h(n-2) = f(n-2)-g(n-2) <= n-1 - (n-1) = 0$$ so by intermediate value theorem, $h(x) = 0$ for some $c\in[1,n-2]$

We want to show that $c$ must be an integer. Suppose it is not can integer, then we have $a<c<a+1$ where $a$ and $a+1$ are consecutive integers. By definition of $h(c)=0$ we have $f(c)=g(c)$.

Note that $|g(a+1)-g(a)|=1$ and $f(a+1)-f(a)=1$. In order for the two function $f$ and $g$ to intersect at $x=c$, we must have $f(a)=g(a+1)$ and $g(a)=f(a+1)$. However, because $f(a)$ and $g(a)$ must be both even or both odd, this can't be true, so $c$ must be an integer.

Now we have proved the case if the cat starts at an even position then we mmust find it during our first traversal.

The second case is that if the cat starts at an odd position. In this case, we assume we haven't find the cat yet after the first traversal. Now we re-number the doors in reverse order and now the cat must be in an even position. It becomes an identical scenario to the first case.

Answer 3

Here's a proof for 5 doors, maybe you can figure out how to generalize?

Note that, at any point, the game state is characterized by the subset $S$ of doors which the cat cannot occupy, based on what's occurred.

Also note that knowing more information is always at least as good: If $S \subseteq S'$, then any winning set of moves starting from $S$ will also win starting from $S'$.

At the beginning, $S = \emptyset$.

First Move: Opening any door besides $2$ or $4$ will result (after the cat moves) in $S = \emptyset$, so these are useless moves. Opening doors $2$ or $4$ results in $S = \{1\}$, $S = \{5\}$ (respectively). By symmetry, both are equally good moves, so say we pick door 2, resulting in $S = \{1\}$.

Second Move: At the next stage, picking door $2$ results in $S = \{1\}$ (A first-move state), door $4$ results in $S = \{5\}$ (equivalent to a first-move state), and door $5$ results in $S = \emptyset$ (a zero-move state), so the pick must be door $3$ resulting in $S = \{2\}$.

Third Move: At the next stage, picking doors $3$ or $5$ result in $S = \emptyset$, picking door $1$ results in $S = \{1\}$ (a first-move state), so the correct play is door $4$ resulting in $S = \{1,3,5\}$.

Fourth Move: By symmetry we can open either door $2$ or $4$, say door $4$ resulting in $S = \{2,4,5\}$.

Fifth Move: Opening door $1$ results in $S = \{1,3,5\}$, a third-move state, so we open door $3$, yielding $S = \{1,3,4,5\}$.

Sixth Move: There is one spot left, so we win.

General Thoughts: For a subset $S$, define the order of $S$, $o(S)$ to be the fewest number of moves it takes to obtain a state $S'$ with $S \subseteq S'$. A set is $k-$maximal if $o(S) = k$, and $S$ is not a proper subset of any set $S'$ with $o(S') = k$. It is clear that any $(k+1)-$maximal set can be obtained in a single move from a $k-$maximal set, so to characterize $(k+1)-$maximal sets, it suffices to consider all possible moves from $k-$maximal sets. Also, given $S$, opening a door in $S$ cannot be better than opening a door not in $S$. With this discussion, the above analysis in the 5-door case shows that the $k-$maximal sets are: (up to reflection)

$k = 0: \emptyset$

$k = 1: \{1\}$

$k = 2: \{2\}$

$k = 3: \{1,3,5\}$

$k = 4: \{2,4,5\}$

$k = 5: \{1,3,4,5\}$

$k = 6: \{1,2,3,4,5\}$

In the general case, there might be an easy characterization of $k-$maximal states, which you can prove by induction.

Answer 4

A diagram goes a long way in understanding the solution. Draw the seven doors in a row, and indicate which one you're opening (I've done so below using the number of the door being opened). At each step, mark where the cat cannot possibly be; for example, in the second step, the cat cannot be behind door $\#1$ because then you would have already found it in the previous step. I've marked such doors with an $\times$.

As you can see, the cat will be caught by the strategy you mentioned. Hopefully the diagram will make it easier to see how to put together a formal proof as others have done.

You can also readily see that the strategy is not unique (for example, try $(2,3,4,5,6,2,3,4,5,6)$ instead.)

      Doors

     -2-----  
     x-3----
T    -x-4---
i    x-x-5--
m    -x-x-6-
e    x-x-x6-
     -x-x5xx
     x-x4xxx
     -x3xxxx
     x2xxxxx

Answer 5

Note: The original poster said "I understand why this solution is correct". What he wanted was a proof that the solution is optimal. I find it strange that none of the responses here give any proof of the optimality for the original 7 doors puzzle. The proof of optimality for 5 doors in this response seems quite convoluted.

I will now sketch a proof of the minimality of $2(n-2)$ moves to catch the cat.

First, we can draw out the situation in a grid such that the $i^\text{th}$ row represents the doors at the $i^\text{th}$ step and plot the doors opened by the strategy on this grid by a slash. We also color the cells red or blue in a checkerboard pattern. For example, one of the optimal solutions are:

time \ door	1	2	3	4	5	6	7
1		̸
2			̸
3				̸
4					̸
5						̸
6						̸
7					̸
8				̸
9			̸
10		̸

Now note that if there is a path from the top to the bottom that always goes from the previous cell to the cell diagonally left-and-down or right-and-down, then the strategy misses such a cat. The intuition is that these paths are all of one color, red or blue, so if the path starts on a red cell, it will never be blocked by a slash on a blue cell and vice versa.

Suppose there are less than $2(n-2)$ slashes. Then one of the colors, call this $C$, will have less than $n-2$ slashes. Consider the middle $n-2$ columns. One of these columns $x$ will have no slashes on color $C$. Note that a row cannot have more than one slash because you cannot open two doors at the same time. In every row, pick a cell of color $C$ which is in one of the columns $\left\{x-1,x,x+1\right\}$ and has no slash (this is clearly always possible). Together, these cells form a path for the cat to escape.

In the following example, the red cells have fewer than $n-2$ slashes, and the asterisks mark a path for the cat to follow.

time \ door	1	2	3	$x$=4	5	6	7
1		̸	*
2			̸	*
3			*	̸
4				*	̸
5			*			̸
6				*		̸
7			̸		*
8		̸		*
9			*		̸

Answer 6

Here's a proof of optimality. What's the worst nightmare of a corridor cat-catcher? Psychic cats with foreknowledge of the sequence your strategy will open the doors in. The idea is to construct a decision rule that such an opponent can follow to evade your moves — like trying to write an AI for your enemy in a computer game, can we make them hard to beat based on just a few simple rules? In particular, sufficiently hard to beat that we need at least $2(n-2)$ turns to catch such a cat? If so, then a winning strategy which opens only $2(n-2)$ doors must be optimal.

There are $n-2$ doors not at the ends of the corridor, i.e. the doors numbered $\{2, 3, \dots, n-1\}$, and it turns out each of them must be opened at least twice, or else we can write a ruleset that creates an uncatchable cat. Therefore the minimum number of openings is indeed at least $2(n-2)$. In fact we'll see each non-end door must be opened at least once on an even-numbered turn and at least once on an odd-numbered turn.

Suppose there is one of these non-end doors you never open. Let's call it $x$. Then a cat knows it is always safe behind that door, and can use it as a kind of "home square" that it spends every other turn behind. (If the cat spends all its odd-numbered turns behind door $x$ we'll call it "odd-homed" at $x$; similarly for "even-homed".) On the alternate turns, it has a choice of two adjacent doors $x-1$ and $x+1$ to temporarily hide behind. Since you can open at most one of them on any given turn, then a psychic cat can just choose the other adjacent door if you do so. So a cat that's odd-homed at $x$ can follow a decision rule like "spend odd turns behind the safe door $x$, and even turns behind $x+1$ unless that door is being opened on that turn, in which case hide behind $x-1$ instead". You can't catch that cat, so a strategy that never opens door $x$ is doomed.

Now suppose you open door $x$ only once. If you do so on an odd-numbered turn, then $x$ is still a safe square on all even-numbered turns and a psychic cat even-homed at $x$ is uncatchable. It can safely follow the rules "spend even turns behind the safe door $x$, and odd turns behind $x+1$ unless that door is being opened on that turn, in which case hide behind $x-1$ instead". But open $x$ only on an even turn, and the cat can evade you by being odd-homed at $x$. Clearly you'll have to open door $x$ on both an even-numbered turn and on an odd-numbered turn to guarantee catching this pesky cat, and this is true for each $x \in \{2, 3, \dots, n-1\}$. This is enough to prove at least $2(n-2)$ openings are required to defeat cats following odd- or even-homed rulesets. Here's an illustration of how the rulesets work:

Key: door symbols represent which door is opened on that turn; some rows have no door shown because a door other than $\{x-1,x,x+1\}$ was opened that turn. Colour-coding shows times when the cat follows one of the "dodging rules", and which door opening they are responding to. Cats with a blank background are just following their default rule; door openings with a blank background have no effect on the cat's behaviour.

---

EDIT: Now can we use this idea to find the optimal solutions?

The odd-homed and even-homed cats are sufficiently hard to beat that we now know at least $2(n-2)$ openings are required, and if such a strategy exists, then any given non-end door $x \in \{2,3,4,\dots,n-1\}$ must be opened exactly once on an odd turn (let's call that turn number $T_O$) and exactly once on an even turn ($T_E$). Unfortunately, any strategy that opens every non-end door once on an even turn and once on an odd turn is sufficient to beat these opponents, but it's clear many of these strategies will fail against more cunning and mobile cats. In other words, the cat rulesets we considered so far are not difficult enough to beat that they can show us what the optimal strategy actually looks like. We need to make our adversary a bit tougher.

The odd-homed and even-homed rulesets were as tricky as it gets if the cat is limited to three doors, so let's grant the freedom to use a fourth door in emergencies. For $x \in \{2,3,4,\dots,n-2\}$ there is another door two to the right, at $x+2$, which a "right-dodging" cat can hide behind when they need to avoid their "home" door $x$. Getting there and back means they must occupy door $x+1$ in the turns before and after. Similarly for $x \in \{3,4,\dots,n-2,n-1\}$, a "left-dodging" cat homed at $x$ can hide behind $x-2$ when $x$ is opened on a turn they'd usually be scheduled to be there, passing through $x-1$ in the turns before and after.

So a right-dodging cat odd-homed at $x$ can follow a ruleset like "spend odd turns behind the safe door $x$, except on turn $T_O$ when we hide behind door $x+2$ instead. Spend even turns behind $x+1$ unless that door is being opened on that turn, in which case try to hide behind $x-1$, but we must spend turns $T_O - 1$ (if $T_O > 1$) and $T_O + 1$ hiding behind door $x+1$ in order to reach door $x+2$ on turn $T_O$ and return to door $x$ on turn $T_O + 2$". Such a cat can no longer be caught behind door $x$, and is now safe on all odd turns! Our only chance to catch it is to also open door $x+1$ on one of the turns $T_O \pm 1$. Similarly, a right-dodging cat even-homed at $x$, but which hides behind $x+2$ on turn $T_E$, can be caught only behind door $x+1$ on turns $T_E \pm 1$. Left-dodging cats can be caught only behind door $x-1$ on turns $T_O \pm 1$ (if odd-homed) and $T_E \pm 1$ (if even-homed).

We now have to beat four kinds of adversary, based on whether they are odd- or even-homed and whether they dodge left or right:

I'll call the doors that are neither at nor adjacent to the ends of the corridor, i.e. doors $\{3,4,\dots,n-3,n-2\}$, the "mid-corridor" doors. If $x$ is a mid-corridor door, then it can be home to both left-dodging and right-dodging cats, so on the turns before and after we open $x$, we must also open $x-1$ and $x+1$ to ensure either kind of cat is caught. This means we must open the three doors in sequence, either $x-1, x, x+1$ ("sweeping up") or $x+1, x, x-1$ ("sweeping down"). In particular, we cannot open $x$ unless we opened one of its adjacent doors the turn before — which means the optimal strategy cannot start by opening a mid-corridor door — and our next move is determined by the previous one, in such a way as to keep the sequence of door openings moving in the same direction: we are propagating a wave of openings either leftwards or rightwards along the corridor.

We now know that the first door to open must be adjacent to the corridor ends, so either $2$ or $n-1$. Let's say our first turn opens door $2$; in case there was a right-dodging cat odd-homed at door $2$, we must spend the second turn opening door $3$. But this is a mid-corridor door, so afterwards our third turn must be used to open door $4$ (in case there was a right-dodging cat even-homed at $3$), then the fourth turn on $5$, and so on until we open door $n-1$ on turn $n-2$, thus completing a sweep "up" the corridor.

What happens on the next turn, $n-1$? We previously established we couldn't open a mid-corridor door unless we opened an adjacent door the turn before. We just opened door $n-1$ so the only mid-corridor door we need to consider is door $n-2$, but we opened it two turns ago. The optimal strategy required us to open it once on an even turn and once on an odd turn, not on two even or two odd turns. So we must either open door $n-1$ again immediately, or repeat our first turn and return to door $2$. Note that if $n$ is even, then $n-1$ is an odd-numbered turn, so it is not optimal to return to door $2$ which was previously opened on an odd-numbered turn. If $n$ is odd, then $n-1$ is an even-numbered turn and we can return to door $2$, hence triggering another wave that sweeps up the corridor. On the other hand, we can open door $n-1$ again regardless of the value of $n$, since opening it on turns $n-2$ and $n-1$ is guaranteed to be one odd turn and one even turn. By similar reasoning, this triggers a wave that sweeps down the corridor, back to door $2$.

Alternatively we could have opened door $n-1$ on the first turn; in case there was a left-dodging cat odd-homed at $n-1$, then the second move must be to open the mid-corridor door $n-2$, which must then be followed by $n-3$, and so on. But the symmetry of the situation means this is just a reflection of what happened when we started at $2$; one way to see that starting with door $2$ was without loss of generality is to renumber the doors from right to left instead of left to right, so that door $n-1$ is relabelled as door $2$.

What we have shown is that if there is an optimal solution that catches the cat within $2(n-2)$ turns, then it must be one of:

• sweep up the corridor then back down again, $(2, 3, \dots, n-2, n-1, n-1, n-2, \dots, 3, 2)$,
• if $n$ is odd, sweep up the corridor twice, $(2, 3, \dots, n-2, n-1, 2, 3, \dots, n-2, n-1)$,
• reflections of the above, i.e. sweep down the corridor then back up (for any $n$) or sweep down the corridor twice (for odd $n$).

It is clear that any of these strategies will defeat any feline adversary following one of the six rulesets considered so far, since we have ensured

• each non-end door is opened on one odd turn and one even turn,
• whenever we opened a door that could be home to a right-dodging cat, we opened the door immediately to the right either on the turn before or the turn after,
• whenever we opened a door that could be home to a left-dodging cat, we opened the door immediately to the left either on the turn before or the turn after.

We haven't yet shown that these are the optimal strategies, because we haven't proven they actually work against every cat, not just the six opponents we designed. To check this, here's a proof by induction of the statement "if we sweep up the corridor from door $2$ to door $n-1$, then at the moment we open door $k$ (i.e. before we close it again and give the cat its chance to move before our next turn) any cat which started behind an even-numbered door, and hasn't been caught yet, will be an even number of squares to the right of door $k$, so behind one of doors $k+2, k+4, \dots$."

The base case is trivially true when $k=2$: when we open that door first, we would catch the cat if it started behind door $2$ and it would be an even number of squares to the right if it started behind one of doors $4, 6, 8, \dots$. Now suppose the statement was true when we opened door $k-1$. When we opened that door any cat that started behind an even door was now behind one of doors $k+1, k+3, \dots$. When we close that door and the cat moves, it must reach one of doors $k, k+2, k+4, \dots$. When we open door $k$, then we will catch the cat if it is there, and otherwise it must be behind one of doors $k+2, k+4, \dots$, so the statement is also true for door $k$. So by the principle of induction, we see the statement is true up to $k=n-1$. But when we complete our sweep by opening door $n-1$, there are no longer any doors an even number to the right. Hence every cat which started behind an even door has been caught in our first sweep up the corridor.

What about any cat that started behind an odd door? If $n$ is even, then after $n-2$ turns (allowing the cat to move after each turn), the cat will have made an even number of moves and be behind an odd door again. We know we need to sweep back down the corridor, from $n-1$ to $2$. If we now renumber the doors from right to left, odd doors that might hide the cat are relabelled as even doors, and we are effectively sweeping up from $2$ to $n-1$ again, so can apply the previous proof and are guaranteed the cat will have been found by the end of our second sweep. On the other hand, if $n$ is odd, then any cat that started behind an odd door will end up behind an even door after $n-2$ turns. Therefore sweeping up from $2$ to $n-1$ a second time is guaranteed to find the cat. Alternatively, we could sweep back down from $n-1$ to $2$. This time if we renumber the doors from right to left, for odd $n$ the even doors the cat could be behind are relabelled as even again. So again the second sweep is guaranteed to find the cat.

Finally, it's clear from symmetry, e.g. by reversing the numbering, that the "reflected" solutions (sweep down then up, or sweep down twice for odd $n$) are also guaranteed to find the cat, regardless of whether it started behind an even or odd door.

Overall, we have shown all of the potential strategies we found to be valid; they all involve opening the minimal number of $2(n-2)$ doors so are all optimal; and we have previously shown that no other strategies can open this few doors and still be guaranteed to catch the cat. Therefore we have found the complete set of optimal strategies.