MINIMAX RENDEZVOUS ON THE LINE

Suppose that n players are placed randomly on the real line at consecu tive integers, and faced in random directions, Each player has maximum speed one, cannot see the others, and doesn't know his relative posit ion. What is the minimum time M(n) required to ensure that all the pla yers can meet together at a single point, regardless of their initial placement? We prove that M(2) = 3, M(3) = 4, and M(n) is asymptotic to n/2. We also consider a variant of the problem which requires players who meet to stick together. and find in this case that three players require 5 time units to ensure a meeting. This paper is thus a minimax version of the rendezvous search problem, which has hitherto been stu died only in terms of minimizing the expected meeting time.