4
$\begingroup$

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!

$\endgroup$
4
  • 1
    $\begingroup$ 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 ? $\endgroup$
    – zwim
    Sep 18, 2017 at 22:11
  • $\begingroup$ @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. $\endgroup$
    – Scatk.1
    Sep 18, 2017 at 22:16
  • $\begingroup$ @Scatk.1 Why did you edit the question to remove all traces of the actual question? $\endgroup$
    – Erick Wong
    Sep 19, 2017 at 21:07
  • $\begingroup$ @Scatk.1 If you are still interested in the answer, take a look at mine! $\endgroup$ Feb 10, 2021 at 16:27

6 Answers 6

6
$\begingroup$

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 馃敶 馃數 馃敶* 馃數 馃敶谈 馃數 馃敶
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Théophile
    Feb 10, 2021 at 18:45
  • 3
    $\begingroup$ @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. $\endgroup$ Feb 11, 2021 at 4:41
  • $\begingroup$ 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. $\endgroup$
    – Théophile
    Feb 11, 2021 at 5:36
  • 3
    $\begingroup$ @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. $\endgroup$ Feb 11, 2021 at 17:52
  • $\begingroup$ That's fair; thanks for the compromise. $\endgroup$
    – Théophile
    Feb 11, 2021 at 18:10
2
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ You can take a look at my answer for an actual proof... $\endgroup$ Feb 10, 2021 at 16:30
2
$\begingroup$

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
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Sep 19, 2017 at 1:27
  • 3
    $\begingroup$ @Théophile you can take a look at my answer for an actual proof... $\endgroup$ Feb 10, 2021 at 16:29
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – Scatk.1
    Sep 19, 2017 at 0:02
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 19, 2017 at 0:31
  • $\begingroup$ 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)$. $\endgroup$ Sep 19, 2017 at 0:52
  • 2
    $\begingroup$ @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. $\endgroup$ Feb 10, 2021 at 16:25
  • $\begingroup$ "Yes I would say so, considering that we always optimize it each step" - I don't think that's necessarily convincing without explaining why a non-greedy approach can't sacrifice some performance at one step in return for better performance at a subsequent step - although I don't think that is too hard to show in this case. I think @user1537366 and I have both submitted answers that prove optimality, but in quite different ways to your answer, so it's interesting to see a range of approaches! $\endgroup$
    – Silverfish
    Jul 31, 2022 at 0:51
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is a cool proof that the "sweep up, then sweep down" strategy is guaranteed to find the cat. But can this method of extending to continuous functions be used to answer the question that was actually asked, i.e. to prove that this strategy is optimal? $\endgroup$
    – Silverfish
    Jul 30, 2022 at 13:38
1
$\begingroup$

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:

Odd-homed and even-homed cats 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:

Right-dodging cats Left-dodging cats

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .