A corridor has 10 rooms on one side. In one of the rooms there is a mouse. Every morning you go into one of the rooms and see if the mouse is there. Every night however, the mouse will go to one of the adjacent rooms through a hole in the wall. The mouse is very clever, and knows exactly which rooms you’re gonna check in the future. Is there a strategy that guarantees that you will be able to catch the mouse?
Solution
The simplest strategy that one can try out is to check the first room in day 1, the second room in day 2, etc. All the way up to the 10th room in day 10. The only way the mouse can survive is if we crossed paths at some point, i.e. one day the mouse was one room ahead of us, and the next day it was one room behind us. The key observation here is that this determines the parity of the room the mouse is in each day: the mouse must be in an even room on odd days, and in an odd room on even days. Therefore, if we repeat the process starting on an even day, we will catch the mouse!
