# Finding the Robot

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?

-
The best-written questions here explain where the problem came from and what you have tried already. Could you please edit your question to add these things? It will help others write answers that are the most helpful to you. –  Carl Mummert Oct 2 '12 at 17:26
As a problem-solving strategy, try solving it first in the case that there are just 3 boxes. Note that the robot's movement is somewhat limited if it is in one of the two boxes at the end of the row. –  Carl Mummert Oct 2 '12 at 17:29
Are the answers assuming that the Robot cannot move in the evening to the box which was examined in the morning? Is this so? –  Mark Bennet Oct 2 '12 at 18:08
@MarkBennet No not neccesary –  Adwait Kumar Oct 2 '12 at 18:10
Day One - EMP Pulse. Now get some rest and stop freting over the robot! –  user43401 Oct 2 '12 at 21:13
show 1 more comment

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.

-
@barto: I find it in the sixth try –  leonbloy Oct 2 '12 at 18:11
Yes, i see. (i deleted my Comment because i saw i was wrong) –  barto Oct 2 '12 at 18:13
Nicely done. For those who are colour blind or prefer words ... If you check box 2 first you get: Check box 2. [Robot not in box 2 at start]: Check box 3. [Robot starting in box 4 now in box 5]: Check box 4. [Get Robot which started in box 5]: Now the Robot is in an odd parity place and will move next to even. And the same strategy played again will get it. –  Mark Bennet Oct 2 '12 at 18:27
This gives a strategy which catches a Robot which started in an even place before one which started in an odd place. This is a good move because there are fewer even places than odd ones. You don't have to check the end boxes at all. Checking the end boxes is inefficient because there is only one way of moving into an end box, and you can catch the Robot by hitting the box next to the end the move before or the move after. –  Mark Bennet Oct 2 '12 at 18:34
I think then that a $2, 3,\ldots,N-1,N-1,\ldots, 3, 2, 2$ is a strategy for $N$ even with $2N-3$ moves: The bot is either "squeezed" at the right end, or crosses our sweep with known parity, hence is then squeezed to the left end and finally caught when leaving the last escape at 1. –  Hagen von Eitzen Oct 2 '12 at 20:25

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.

-
One can ignore the first move because it doesn't restrict the bots position before the second move. Thus the sequence 2, 3, 4, 5, 1, 2, 3, 4, 5 is a sorter winnig strategy. –  Hagen von Eitzen Oct 2 '12 at 17:35
@HagenvonEitzen I don't see how the first move can be ignored. It is needed for the parity and to exclude the possibility of the robot being in $1$. –  EuYu Oct 2 '12 at 17:46
That's right. The first check is needed for the parity. Doing else would be like this: Check boxes 2,3,4,5. Now the robot has moved to box 2 or 4. So, check 2,1,2,3,4 and you find it. (Note that with the 1,2,3,4,5,1,2,3,4,5-solution, the 5 at the end isn't necessary, so it becomes 1,2,3,4,5,1,2,3,4.): 9 checks are enough –  barto Oct 2 '12 at 18:04
The bot can be at 1 on the second day if it started at 2. It can be at 2 the second day if it started at 3. It can be at 3 the second day if i tstarted at 4. It can be at 4 the second day, if it stated at 5. It can be at 5 the second day if it started at 4. Hence nothing is gained by a first day check of box 1. Moreover, the claim that 1,2,3,4,5,1,2,3,4 is a winning strategy also says by symmetry that my suggestion 2,3,4,5,1,2,3,4,5 is a winning strategy. –  Hagen von Eitzen Oct 2 '12 at 20:18