A cat is hiding in one of five boxes that are lined up in a row. The boxes are numbered 1 to 5.
Each night the cat hides in an adjacent box, exactly one number away. Each morning you can open a single box to try to find the cat.
Can you win this game of hide and seek? What is your strategy for finding the cat?
Bonus: What if there are n boxes in a row?
Tech companies like Google and Microsoft have been known to ask this question during interviews. Can you figure it out? Watch the video for a solution.
Can You Solve The Hiding Cat Puzzle? Tech Interview Question
Or keep reading.
(Editorial note: I started working on this problem 1 month ago. Completely independently Alex Bellos at The Guardian posted the 7 door version, using a cat hidden behind a door. If you read that, sorry it’s spoiled. It’s a coincidence we both used cats; I had already finished my video and post before he posted his puzzle. If it was based on his post, I would be up-front about it. I am especially careful since lately many people are using my puzzles without any attribution–it would be nice if they could link to me as I have linked to Alex’s puzzle. In any case, hopefully you’ll like my video presentation and comprehensive solution of n doors.)
. "All will be well if you use your mind for your decisions, and mind only your decisions." Since 2007, I have devoted my life to sharing the joy of game theory and mathematics. MindYourDecisions now has over 1,000 free articles with no ads thanks to community support! Help out and get early access to posts with a pledge on Patreon.
.
.
.
.
.
.
M
I
N
D
.
Y
O
U
R
.
D
E
C
I
S
I
O
N
S
.
P
U
Z
Z
L
E
.
.
.
.
Answer To The Hiding Cat Riddle
You might approach the puzzle by solving a simpler version: imagine the cat is hiding in one of 3 boxes in a row.
Imagine you check box 2 on day 1. If you do not find the cat, then you know the cat must have started in box 1 or 3. In that case, the cat must move to box 2 at night. So check box 2 on day 2 and you will find the cat for sure!
The key to the puzzle is you learn information after you open a box. If you choose wisely, you can eliminate boxes until you can deduce where the cat has to be.
The 5 box version is slightly more complicated as there are more possibilities. But the same kind of logic holds: the cat’s movements are limited. A cat in box 1 has to move to box 2 the next day; a cat in box 5 has to move to box 4 the next day. Furthermore, the box number the cat occupies alternates between even and odd numbers.
We first devise a strategy to catch a cat that starts in an even numbered box. Then we can apply that strategy again, which will catch a cat that started in an odd numbered box.
Here is a strategy that will work for sure. Inspect box 2, then box 3, then box 4. If you have not found the cat, then repeat: inspect 2, 3, then 4. You will certainly find the cat by the 6th time you check.
Why is that?
Let’s assume the cat starts in an even box, 2 or 4.
Day 1: you check box 2. If the cat is in 2, you find the cat. Otherwise, the cat must be in box 4.
Day 2: you check box 3. You will catch the cat if it moved from 4 to 3. But you will miss it if the cat moved from 4 to 5.
Day 3: you check box 4. As the cat was previously in 5, it must have moved to 4. So you will catch the cat.
The above strategy works if the cat started in an even numbered box. But the cat might have been in an odd numbered box 1, 3, or 5.
In that case, after 3 days of checking, you know the cat is now in an even numbered box. If the cat started in 1, 3, or 5, then on night 1 the cat would move to an even box (2 or 4); on night 2 the cat would move to an odd box (1, 3, or 5); and on night 3 the cat would move to an even box (2 or 4).
Thus, on the morning of day 4, you know the cat is in an even numbered box. So now you can repeat the strategy outlined above: check the boxes 2, 3, 4. You will find the cat for sure!
The strategy 2, 3, 4 is sure to catch a cat in an even box. An equivalent strategy is to check 4, then 3, then 2. This works for exactly the same reason due to the symmetry of the boxes in a line.
Both strategies 2, 3, 4 and 4, 3, 2 will catch a cat in an even box. And if either fails after 3 days, then you can repeat either strategy. Thus there are 4 equivalent ways to catch the cat:
2, 3, 4, 2, 3, 4
2, 3, 4, 4, 3, 2
4, 3, 2, 4, 3, 2
4, 3, 2, 2, 3, 4
It will be convenient to visualize the strategy 2, 3, 4, 4, 3, 2, so let us use that for the continuing discussion.
Furthermore, the idea of checking boxes from 2 to n – 1 and then checking the reverse will also work when n is an even number.
Another explanation: process of elimination
Here is another way to understand the strategy of checking 2, 3, 4, 4, 3, 2.
On day 1, you check box 2. If the cat is not in box 2, then there is no way the cat could be in box 1 the next day.
On day 2, you check box 3. You already know the cat is not in box 1 on this day, and if the cat is not in box 3, then there is no way for the cat to be in box 2 the next day.
On day 3, you check box 4. Since the cat is also not in box 2, there is no way it can move to either box 1 or box 3 the next day. Furthermore, if the cat is not in box 4, it also cannot move to box 5 the next day.
Therefore, you know the cat cannot be in box 1, 3, or 5 for the start of day 4. It must be in 2 or 4 to start day 4. In other words, you know the cat is in an even numbered box.
On day 4, you check box 4. If the cat is not there, then you know the cat must have been in box 2, and it can move to box 1 or 3.
On day 5, you check box 3. If the cat is not there, you know the cat must have moved to box 1 the night before, so now the cat has to move to box 2 the next day.
On day 6, you check box 2 and the cat has to be there.
Visualization
Here is a grid that shows the possible cat positions for each day.
You eventually eliminate possible positions for the cat until you find its location on the 6th day.
Solving for 4 boxes
Suppose cat starts in an even box (2 or 4).
First you check box 2. If the cat is there you win. If not, then you know the cat is in box 4 and it will move to box 3.
On day 2, you check box 3. You will catch the cat.
However, the cat might have started in box 1 or 3. After day 1, the cat would move to 2 or 4. After day 2, the cat would move to box 1 or 3. Now there is a twist: the cat is in an odd-numbered box. In order to catch it, you have to guess an odd number box.
So you cannot repeat checking box 2 then box 3. You have to check box 3 on day 3. If you catch the cat, you are done. Otherwise, you know the cat is in box 1 and it will move to box 2. So you check box 2 on day 4.
Thus, the strategy is 2, 3, 3, 2. Alternately you could have checked 3, 2, 2, 3.
In either case, you need to reverse the sequence on the second half of the search.
The key to the solution is that you need to guess an even box when the cat is in an even box. This will makes (your guess – cat box) an even number every single day–this means you never miss the cat bu just one box.
Equivalently, you need to guess an odd box when the cat is in an odd box. This makes (your guess – cat box) an even number every single day, so you again never miss the cat by just one box.
Generalization
The strategy can be generalized to any number of boxes.
Step 1: Check the boxes 2, 3, 4, …, n – 1 (the strategy surely finds a cat that started in an even numbered box on day 1).
Step 2: If that does not work, do search n – 1, n – 2, …, 4, 3, 2 (the strategy surely finds a cat that started in an odd numbered box on day 1).
You can also reverse steps 1 and 2 to find the cat.
And if n is odd, you can also perform the search in step 1 twice, or the search in step 2 twice, to find the cat.
Python implementation
Alexander recreated the puzzle here: https://github.com/SirDrone/Cat_Puzzle
Sources
http://gurmeet.net/puzzles/fox-in-a-hole/
https://www.theguardian.com/science/2017/jul/03/did-you-solve-it-are-you-smarter-than-a-cat
https://somemathematicalmusings.wordpress.com/2016/04/08/the-subterranean-fox/
https://www.checkmyworking.com/2011/12/solving-the-princess-on-a-graph-puzzle/
https://www.youtube.com/watch?v=4fudkLW9pC4
http://www.win.tue.nl/~wstomv/puzzles/vampire-hunt.pdf
https://mathoverflow.net/questions/29323/math-puzzles-for-dinner/29598#29598
http://bl.ocks.org/azundo/5941503
http://www.cseblog.com/2010/01/finding-hermit.html
https://wordplay.blogs.nytimes.com/2014/01/27/princess/?_r=0
http://www.garyhewitt.net/nyt/princess.html
http://trustyservant.com/archives/7146
https://ubpdqnmathematica.wordpress.com/2014/02/01/up-and-down-the-mountain/
https://thinkwitty.com/2017/10/solution-to-microsoft-puzzle-fox-in-a-hole.html
MY BOOKS
If you purchase through these links, I may be compensated for purchases made on Amazon. As an Amazon Associate I earn from qualifying purchases. This does not affect the price you pay.
Book ratings are from January 2023.
(US and worldwide links)
https://mindyourdecisions.com/blog/my-books
Mind Your Decisions is a compilation of 5 books:
(1) The Joy of Game Theory: An Introduction to Strategic Thinking
(2) 40 Paradoxes in Logic, Probability, and Game Theory
(3) The Irrationality Illusion: How To Make Smart Decisions And Overcome Bias
(4) The Best Mental Math Tricks
(5) Multiply Numbers By Drawing Lines
The Joy of Game Theory shows how you can use math to out-think your competition. (rated 4.3/5 stars on 290 reviews)
40 Paradoxes in Logic, Probability, and Game Theory contains thought-provoking and counter-intuitive results. (rated 4.2/5 stars on 54 reviews)
The Irrationality Illusion: How To Make Smart Decisions And Overcome Bias is a handbook that explains the many ways we are biased about decision-making and offers techniques to make smart decisions. (rated 4.1/5 stars on 33 reviews)
The Best Mental Math Tricks teaches how you can look like a math genius by solving problems in your head (rated 4.3/5 stars on 116 reviews)
Multiply Numbers By Drawing Lines This book is a reference guide for my video that has over 1 million views on a geometric method to multiply numbers. (rated 4.4/5 stars on 37 reviews)
Mind Your Puzzles is a collection of the three "Math Puzzles" books, volumes 1, 2, and 3. The puzzles topics include the mathematical subjects including geometry, probability, logic, and game theory.
Math Puzzles Volume 1 features classic brain teasers and riddles with complete solutions for problems in counting, geometry, probability, and game theory. Volume 1 is rated 4.4/5 stars on 112 reviews.
Math Puzzles Volume 2 is a sequel book with more great problems. (rated 4.2/5 stars on 33 reviews)
Math Puzzles Volume 3 is the third in the series. (rated 4.2/5 stars on 29 reviews)
KINDLE UNLIMITED
Teachers and students around the world often email me about the books. Since education can have such a huge impact, I try to make the ebooks available as widely as possible at as low a price as possible.
Currently you can read most of my ebooks through Amazon's "Kindle Unlimited" program. Included in the subscription you will get access to millions of ebooks. You don't need a Kindle device: you can install the Kindle app on any smartphone/tablet/computer/etc. I have compiled links to programs in some countries below. Please check your local Amazon website for availability and program terms.
US, list of my books (US)
UK, list of my books (UK)
Canada, book results (CA)
Germany, list of my books (DE)
France, list of my books (FR)
India, list of my books (IN)
Australia, book results (AU)
Italy, list of my books (IT)
Spain, list of my books (ES)
Japan, list of my books (JP)
Brazil, book results (BR)
Mexico, book results (MX)
MERCHANDISE
Grab a mug, tshirt, and more at the official site for merchandise: Mind Your Decisions at Teespring.
