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 looking for the mouse. 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 going to check in the future. Is there a strategy guaranteeing that you’ll 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!
