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

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!

Solution 1:

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:

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.

Solution 2:

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.

Solution 3:

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