Can you catch the thief?

Question

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 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 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.

Answer 1

This is a very nice 2-dimensional variation of this question.

If you have rooms 1 to 6 in a row, and the thief starts in an even numbered room in the row, then you will find him if you check the rooms 2, 3, 4, 5 in that order. In the traditional 1-dimensional puzzle you would then follow it with a sweep in the opposite direction (5,4,3,2) which would catch him if he started in an odd-numbered room. In this puzzle the thief moved to a different floor at that point however.

You can therefore apply the same kind of sweep over the floors. That is to say, if you sweep the central 4x4 square left to right, bottom to top (8,9,10,11; 14,15,16,17; 20,21,22,23; 26,27,28,29) then you will find the thief if he started on an even floor and even column.

You can then do the same sweep in left-right mirror image (11,10,9,8; 17,...). This finds the thief if he started on an even floor but an odd-numbered room.

Lastly you do the same two sweeps above but mirrored vertically. This will catch the thief if he started on an odd floor, even room or on an odd floor, odd room. One of the four combinations of even and odd rooms and floors must be the case, so one of the four sweeps will find the thief. In total 64 rooms are checked.

Answer 2

I took the practical approach and came up with a strategy that could be optimal (I have not tried to prove it).

In the worst case scenario it takes:

64 nights to catch the thief.

I made a drawing to show my strategy. The yellow squares are the rooms the police officer looks into that night, the black squares are rooms in which the thief logically cannot be.

On day 64 all rooms but two have been eliminated, meaning that if the police officer has not found the thief already, he will find him on that day.

Answer 3

I don't know how to do the exact maths (maybe someone else can help me out) but:

Due to the boundary limitations, my first instincts are that it would average out that the thief would spend most time in the centre-most rooms (15,16,21,22) as they have to move away from the boundaries.

If the number of rooms in a row/column were odd then it would be easy to suggest always checking the room at the very centre but in this case it is even so there are 4 possible centre rooms.

Therefore you could either pick one of those rooms at random and always choose that room to check, or you could cycle round picking a different room of the 4 each night, or pick a room at random out of the 4 each night.

However, because he is far more likely to move left or right to the centre than up or down, it might be better to pick one of the centre rows and then choose one of the above choices but limit it to the one row.