Chasing a monster on a $3 \times 3$ grid 
There are nine rooms as shown below $$\begin{array}{|c|c|c|}\hline1&2&3\\\hline4&5&6\\\hline7&8&9\\\hline\end{array}.$$ A monster is in one of the rooms. Each turn, the people open $k$ different rooms and check if the monster is inside. If the monster isn’t seen, it will go to another room that has a common side with the previous one.
Find $k$ for which people can guarantee finding the monster.

I proved $k=3$ works.
First, while the monster is hidden, its room number will go in a cycle of odd and even.
Open rooms $(2,4,6);(2,4,6);(5,7,9);(5,7,9)$ in the first four turns in this order. I’ll prove this works by separating the problem into two cases:

*

*The room number of the monster is odd-even-odd-even in the first four turns. Then in the second turn the monster must be in room $8$ or else it is found. So in the third turn the monster must be found.

*The room number of the monster is even-odd-even-odd in the first four turns. Then in the third turn the monster must be in room $8$ or else it is found. So in the fourth turn the monster must be found.

But how to prove $k<3$ doesn’t work?
 A: Suppose the monster is even-numbered. Open rooms 2 and 4. If the monster isn't caught, it is now odd-numbered and not in room 1. Now open rooms 3 and 5. If the monster isn't caught, it is now even-numbered and not in room 2. Open rooms 4 and 6. If the monster isn't caught, it is in room 8, and becomes an odd numbered monster in room 5, 7, or 9. Open rooms 5 and 7. If the monster isn't caught, it is in room 9, and becomes an even-numbered monster in room 6 or 8. Open those doors. If the monster isn't caught, it is an odd-numbered monster, and becomes an even-numbered monster. Repeat to catch him.
A: (@eyeballfrog posted an essentially identical answer shortly before I did. I'll leave this up just as a different way of describing it.)
When $k=2$, the people can win within 10 turns:
$$(2,4); (3,5); (6,8); (5,7); (2,4); (2,4); (3,5); (6,8); (5,7); (2,4)$$
Let $M_n$ be the number of the monster's room on turn $n$, $1 \leq n \leq 10$.
If $M_1$ is even and the monster stays hidden, then $M_1 = 6$ or $M_1 = 8$. If not found on turn 2, $M_2 = 7$ or $M_2 = 9$, but it can't be in room 1. If $M_2 = 9$ then the monster is found on turn 3. If $M_2 = 7$ the monster can only hide with $M_3 = 4$, then $M_4 = 1$, but then must be found on turn 5.
If $M_1$ is odd, the first five guesses will all miss the monster, but then the monster can't stay hidden for guesses 6 through 10 for the same reasons as above.
A: It is also possible to catch the monster when $k=2$.
Start by checking two rooms adjacent to a corner, say, rooms $2$ and $4$. If you do not catch the monster, on the next turn, you know it is not in room $1$. This is progress.
On the next turn, check rooms $3$ and $5$. Since $1$ was eliminated by the previous turn, this means that all of room $2$'s neighbors are cleared, so on the next turn, we have eliminated room $2$ (but room $1$ is now possible again).
On the third turn, check rooms $4$ and $6$. Since $2$ was eliminated by the previous turn, this implies that all of the neighbors of both rooms $1$ and $3$ have been cleared, so on the next turn, we have eliminated rooms $1$ and $3$.
Continuing in this fashion, you can reach a point where all rooms are eliminated, which means at some point previous you must have caught the monster. I leave the details of fleshing out the rest of this strategy to you, dear reader.

It is also easy to prove $k=1$ is impossible. The monster can evade capture forever while only using the rooms numbered $1,2,4$ and $5$. It survives by using this strategy: move in the cycle $1\to 2\to 4\to 5\to 1\to \dots$ over and over, unless the next room in the cycle is the room that the player will check next turn. In that case, the monster should instead backtrack.
This of course assumes that the monster can read the human's mind. However, even if the monster just randomly moves, there is a finite chance it will follow this strategy for any finite number of turns. Therefore, with $k=1$, there is a finite chance a random monster will evade capture for any period of time, meaning you cannot guarantee capture with $k=1$.
