# 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!

• problem needs precisions : does the cat move to a door adjacent to him or adjacent to the open door ? what about moving to an already open door ? or do we close the door after opening it ?
– zwim
Sep 18 '17 at 22:11
• @zwim Sorry about the unclarity, I've edited the post now. The cat must move the door adjacent to him, we must close the door right after we open it and the cat can move to a door we had just opened. Sep 18 '17 at 22:16
• @Scatk.1 Why did you edit the question to remove all traces of the actual question? Sep 19 '17 at 21:07
• @Scatk.1 If you are still interested in the answer, take a look at mine! Feb 10 at 16:27

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.

• Thank you, this has cleared things up a bit. So your answer also verifies the answer of 2(n - 2). What I am wondering is that would you say that laying the solution out - as you have done in your answer - is sufficient proof for proving that 2(n - 2) is the optimal answer? Sep 19 '17 at 0:02
• Yes I would say so, considering that we always optimize it each step. Which in turn must mean that it's optimized overall. I could formalize this optimization but I felt that it wasn't necessary in this answer when I saw some other answer that did the same thing. Sep 19 '17 at 0:31
• For example, the way we pick a door is to get as many $7$ (or $1$) chances in there as possible if we fail on our pick, because these will only yield one move for the cat instead of two. Similarly we want to avoid going to doors that we've previously opened, because this will just prolong the round, which is unnecessary in every way. These two things are what we can use to optimize as far as I've found, and with them we get the worst-case scenario of $2(n-2)$. Sep 19 '17 at 0:52
• @SamAnderson you said "I could formalize this optimization", but it is not very easy to do so, so you don't actually answer the poster's real question. In my answer, I present a different approach to proving this. Feb 10 at 16:25

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 🔴 🔵 🔴* 🔵 🔴̸ 🔵 🔴
• This question is three and a half years old and has already been answered rather comprehensively. It is in poor taste for you to message all the participants here while denigrating their contributions. Feb 10 at 18:45
• @Théophile I think you are being too harsh there. I was just stating an observation that none of the answers are proofs. Please read the original poster's question again. He does not want to know why the $2(n-2)$ solution works. He wants to know why it is the solution with the least number of moves. So your claim that the question has been "answered rather comprehensively" is totally wrong. Feb 11 at 4:41
• It's great that you've added your own solution; you've clearly taken pains to construct it and illustrate it. My issue is that writing to the other authors to invite them to see an "actual proof" comes across as snarky, as does putting scare quotes around "solutions". I don't want to discourage you from participating, but perhaps next time it would be enough simply to add your answer without messaging everyone. Bear in mind also that some answers (such as mine here) are not intended to be full solutions; they could be hints or just too long to fit in a comment. Feb 11 at 5:36
• @Théophile My issue is that many of the responses seem to have made the same mistake of ignoring what the original poster wants. To be honest, I felt that none of them were helpful to me when I was trying to prove the optimality. Anyway I have changed my opening sentence as per your comments. Hopefully you will be less offended. Feb 11 at 17:52
• That's fair; thanks for the compromise. Feb 11 at 18:10

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.

• You can take a look at my answer for an actual proof... Feb 10 at 16:30

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

• An important thing to note here as well is that $2, 3, 4, 5, 6$ $\equiv$ $6, 5, 4, 3, 2$. Because they are symmetric, both $2$ and $6$ are $1$ door away from reaching a dead-end, and both of them increments/decrements by $1$, so they're logically equivalent and will yield the same performance. Sep 19 '17 at 1:27
• @Théophile you can take a look at my answer for an actual proof... Feb 10 at 16:29

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.