This was a puzzle I recalled from university a couple of years back. I don't know what the original puzzle is but if someone knows it, please let me know so I can credit the source.
You are a police officer and you are in charge of catching a notorious thief. At one point you discover that the thief is hiding out in an abandoned building.
The building consists of 36 rooms in square formation, each floor has 6 rooms. With all rooms numbered the building looks like the following:
+----+----+----+----+----+----+
| 31 | 32 | 33 | 34 | 35 | 36 |
+----+----+----+----+----+----+
| 25 | 26 | 27 | 28 | 29 | 30 |
+----+----+----+----+----+----+
| 19 | 20 | 21 | 22 | 23 | 24 |
+----+----+----+----+----+----+
| 13 | 14 | 15 | 16 | 17 | 18 |
+----+----+----+----+----+----+
| 07 | 08 | 09 | 10 | 11 | 12 |
+----+----+----+----+----+----+
| 01 | 02 | 03 | 04 | 05 | 06 |
+----+----+----+----+----+----+
In order to elude the police the thief has a peculiar way of moving through the building. On the first night the thief enters one of the 36 rooms. Each next night, the thief moves randomly either one room to the left or one room to the right. If there is no room to the left, the thief automatically moves to the right, and vice versa. However, on each fourth move of the thief, the thief moves randomly either a room up or down. Again, if there is no room above the thief he automatically moves down and vice versa. The thief always tries to avoid being captured. So, for example, the thief can take the following path:
14-15-16-15-21-22-23-24-18-17-...
Due to limited manpower you are able to search exactly one room each night.
The question is if you can find a strategy which will catch the thief each time, no matter the path the thief takes and how many nights will it take to catch the thief in the worst case scenario.
