13
$\begingroup$

The Youtube channel MindYourDecisions posted a video about the "Hiding Cat Puzzle". In the puzzle, you have a line of five boxes, one of which contains a cat. You don't know where the cat is, and your goal is to find it. You can look in any box, but each time you do so, the cat moves to an adjacent box without your knowledge. Interestingly, it is possible to find the cat by strategically choosing which boxes to look in. You can watch the video for the solution. I found this puzzle fascinating, and thought about how it might generalize to a grid of boxes. So here is my riddle for you:

You are presented a $10\times 10$ grid of boxes, one of which contains a cat. You may select $n$ boxes to look in, and then the cat moves to an adjacent box without your knowledge. Two boxes are considered adjacent if they touch vertically or horizontally, but not diagonally. After the cat moves, you may choose another $n$ boxes to look in, and then the cat moves again, etc. The question is, what is the lowest number $n$ such that you can be guaranteed to find the cat? And give an example of a successful strategy.

Improve this question
$\endgroup$
7
  • $\begingroup$ Related (to the first part) $\endgroup$
    – Alconja
    Dec 21, 2017 at 2:24
  • $\begingroup$ For NxN grids, you can apply the same strategy as the 2d version as long as you are able to open N boxes. Looking into ways to make it possible with less, but i'm inclined to believe that you can't really go any better than N. $\endgroup$
    – votbear
    Dec 21, 2017 at 2:41
  • 2
    $\begingroup$ @VotBear If you are thinking about treating each row as a "box" and calling that the reduction to the 1d case, it still doesn't quite work. Because it is possible for the cat to remain in the same row, but in the 1d case the cat must move to a different box. If you had a different idea for the reduction, please explain. $\endgroup$
    – Riley
    Dec 21, 2017 at 2:45
  • 1
    $\begingroup$ No, i was thinking of seeing it as a checkerboard, and moving diagonally. instead of "Even" and "Odd" boxes, you'll use "Black" and "White" cells instead. Moving from one diagonal to the other, the most you'll need would be N $\endgroup$
    – votbear
    Dec 21, 2017 at 2:47
  • $\begingroup$ But scratch that, i think i just found a solution using N=2 for a 3x3 grid, so N=(M-1) for MxM grids might be possible. Proving that this applies to all M might be trickier though.. plus 2x2 grids can definitely not be solved with N=1, so i believe N is at least 2. $\endgroup$
    – votbear
    Dec 21, 2017 at 2:47

1 Answer 1

Reset to default
7
$\begingroup$

You can succeed when n =

6

Here's how:

x = cells inspected that turn
o = cells ruled out from previous turns



It should be pretty clear that this process can be continued to fill half of the board with o's, checkerboard style. At this point, repeating the same process with the "opposite parity" takes care of the other half.

Thoughts on proof of optimality:

Here is my scratch work where you select 5 cells per turn. I cannot seem to eliminate more than 13 cells at a time.
This is a possible route to a disproof. For any subset S of cells, let S' be its set of neighbors, that is, cells which are adjacent to at least one cell in S. In order to rule out S, every element of S' must have been previously eliminated or inspected that turn.
To prove that you cannot eliminate 14 cells, it would suffice to prove that any set 14 cells has at least 19 neighbors.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.