20
$\begingroup$

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?

  • 7
    Day One - EMP Pulse. Now get some rest and stop freting over the robot!2012-10-02

3 Answers 3

26

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.

enter image description here

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.

  • 1
    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.2012-10-02
10

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.

  • 1
    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.2012-10-02
1

a quick and dirty python program that checks that there is no solution that finds the robot in 5 days. We can assume that the first check is done with box 1,2 or 3.

from  math import ceil  """ a check is a list of numbers between 1 and 5. The number of the i-th position is the number of the bux that will be checked on the i-th day (python arrays start with index 0, so the first position of an array has index 0  """ def find_robot(days,boxes):     """finds all checks that finds the  robot in `days' days in `boxes' boxes     """      def intersectlist(l1,l2):         """ checks if two lists of equal length have the same value at a poision         """         listsum=0         for pair in zip(l1,l2):             if (pair[0]==pair[1]):                 return(True)         return(False)      def robotfound(checks):         """ tests if list of checks can find all possible robot moves         """         for s in ss:             if not intersectlist(checks,s):                 return(False)         return(True)  # generate all checks       ll=[[i] for i in range(1,ceil(boxes/2)+1)]     for i in range(days-1):         ly=[]         for t in ll:             for j in range(1,boxes+1):                 s=t[:]                 s.append(j)                 ly.append(s)         ll=ly          # generate all moves (including that to boxes with numbers <1 or >5)                                  sx=[[i] for i in range(1,boxes+1)]     for i in range(days-1):         sy=[]         for t in sx:             for j in [-1,1]:                 s=t[:]                 s.append(s[-1]+j)                 sy.append(s)         sx=sy         # filter out invalid moves to boxes <1 or >5      ss=[]     for s in sx:         for val in s:             if val<1 or val>boxes:                 break         else:             ss.append(s)      # printout all checks that find the robot for all possible moves     for c in ll:         if robotfound(c):             print(c) 

The function find robot can be called for different days

>>> find_robot(5,5) >>> find_robot(6,5) [2, 3, 4, 2, 3, 4] [2, 3, 4, 4, 3, 2] >>> find_robot(7,5) [1, 2, 3, 4, 2, 3, 4] [1, 2, 3, 4, 4, 3, 2] [1, 4, 3, 2, 2, 3, 4] [1, 4, 3, 2, 4, 3, 2] [2, 2, 3, 4, 2, 3, 4] [2, 2, 3, 4, 4, 3, 2] [2, 3, 4, 2, 3, 4, 1] [2, 3, 4, 2, 3, 4, 2] [2, 3, 4, 2, 3, 4, 3] [2, 3, 4, 2, 3, 4, 4] [2, 3, 4, 2, 3, 4, 5] [2, 3, 4, 4, 3, 2, 1] [2, 3, 4, 4, 3, 2, 2] [2, 3, 4, 4, 3, 2, 3] [2, 3, 4, 4, 3, 2, 4] [2, 3, 4, 4, 3, 2, 5] [2, 4, 3, 2, 2, 3, 4] [2, 4, 3, 2, 4, 3, 2] [3, 2, 3, 4, 2, 3, 4] [3, 2, 3, 4, 4, 3, 2] [3, 4, 3, 2, 2, 3, 4] [3, 4, 3, 2, 4, 3, 2] 

So there is no solution for 4 days. 2 solutions for 6 days (if we assume the first check is a check of a box with number less or equal 3) and a lot of checks that works if we allow 7 days to find the robots

The function can be called for a different number of boxes

>>> find_robot(2,3) [2, 2] >>> find_robot(3,4) >>> find_robot(4,4) [2, 3, 3, 2] >>> find_robot(5,5) >>> find_robot(6,5) [2, 3, 4, 2, 3, 4] [2, 3, 4, 4, 3, 2] >>> find_robot(7,6) >>> find_robot(8,6) [2, 3, 4, 5, 5, 4, 3, 2] 

For $n$ boxes the sequence $ 2,3,\cdots,(n-1),2,3,\cdots,(n-1)$ will catch the robot. If the robot starts in an even numbered box then the first $2,3,\cdots,n-1$ sequence will catch him:

if the robot start in an even box then the difference of the number of robots box and the number of the box checked is an even number. So at the begin the robot must be in a box with a number higher then the box checked (the box with number 2). On the first day when the robots box number $b_r$ is lower as the number $b_c$ of the box checked , we have $b_r<=b_c-2$ on the day before this day we have $b_r+1>=b_c-1$ a contradiciton

if he starts on an odd numbered box, the second sequence will catch him.

If $n$ is an odd number the sequence $ 2,3,\cdots,(n-1),(n-1),(n-2)\cdots,2$ will catch the robot, too.