riddle of the day

Each morning you may open one door. Each night the cat changes rooms. You need a plan that does not depend on luck.

The Night-Roaming Cat

Strategist
Master plays

Riddle statement

Seven rooms stand in a row, numbered 1 to 7. A cat is hiding in one of them.

Each day you may open one room only. If the cat is there, you find it. Otherwise you close the door and learn nothing more.

Every night the cat must move to an adjacent room: from room 4 it can move to 3 or 5; from an end room it must move inward. It never stays put or skips a room.

Can you devise a plan that guarantees finding it, whatever moves it makes? Explain why your plan works.

Seven consecutive rooms numbered 1 to 7.
Show solution

Solution

Yes. This plan guarantees finding the cat within ten days:

2, 3, 4, 5, 6, 6, 5, 4, 3, 2.

You do not need to open either end room.

First sweep: a cat starting in an even-numbered room.

On days 1–5, inspect rooms 2, 3, 4, 5 and 6. Both the cat’s room and your chosen room change parity each day, so their numbers always have the same parity.

Let xₜ be the cat’s position before the inspection on day t, and qₜ = t + 1 your chosen room. The difference dₜ = xₜ − qₜ is even. It starts nonnegative, since the cat starts in room 2, 4 or 6.

Each night the cat moves by +1 or −1 while your next inspection moves by +1. Thus dₜ changes by 0 or −2. On day 5, the cat is in an even room no higher than 6, which you inspect: d₅ ≤ 0.

An even difference going from nonnegative to nonpositive in steps of 0 or −2 must reach zero. You find the cat on that day.

Second sweep: a cat starting in an odd-numbered room.

If you have not found it, it started in an odd room. After five nightly moves, it is in an even room on day 6.

Inspect room 6 again, then 5, 4, 3 and 2. Now use the difference qₜ − xₜ. It starts nonnegative, changes by 0 or −2, and is nonpositive on day 10: you inspect room 2 and the cat is in an even room at least as high as 2. Again, the difference must reach zero.

Repeating room 6 matters: another night passes and the cat moves, even though you inspect the same room again. This changes which starting class your sweep can catch.