Finding the Robot

Question

There are five boxes in a row. There is robot in any one of these five boxes. Every morning I can open and check a box (one only). In the night, the robot moves to an adjacent box. It is compulsory that he moves. I need a method to ensure that I can catch the robot within ten days. How to do so?

Answer 1

I think 6 tries are enough.

For example: 2,3,4,4,3,2

The diagram (time goes down) shows, in blue, the posible displacements of the robot, the yellow dots are the (failed) tries, the red lines the impossible displacements, the red dot the impossible positions.

Another possible try (perhaps more elegant): 2 3 4 2 3 4

In general: if we have N boxes (N odd) we make a first sweep 2, 3 ... N-1. If we didn't find it, the it's moving with opposite parity. We try again the same sweep (or the mirrored) and we find it in $2 \times (N-2)$ tries (worst case).

Added: The two strategies [2 3 4 2 3 4] and [2 3 4 4 3 2] are equivalent for odd N. But the later works also for even N.

Answer 2

Here's a possible solution. The best way to solve these things is just trying, i think.

Check the boxes in this order: 1,2,3,4,5. If you haven't met the robot yet, the robot must have started in box 2 or 4.

Proof: Suppose he started in box one, then you would have found him the first day.

Suppose it started in box 3, then it moved to 4, then to 5, then to 4, where you find it the forth day.

Suppose it started in box 5. It moves to 4, to 5, to 4, and you find it.

After these 5 days (nights), the robot has again moved to an odd box: 1, 3 or 5. So, check boxes 1,2,3,4,5 again. you will meet the robot, because of the same reason as you didn't met it during the first five days.