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!
Best Answer
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.