Two friends have become separated in a building or shopping mall and wish to meet as quickly as possible. There are $n$ possible locations where they might meet. However, the locations are identical and there has been no prior agreement where to meet or how to search. Hence they must use identical strategies and must treat all locations in a symmetrical fashion. Suppose their search proceeds in discrete time. Since they wish to avoid the possibility of never meeting, they will wish to use some randomizing strategy. If each person searches one of the $n$ locations at random at each step, then rendezvous will require $n$ steps on average. It is possible to do better than this: although the optimal strategy is difficult to characterize for general $n$, there is a strategy with an expected time until rendezvous of less than $0.829n$ for large enough $n$. For $n=2$ and $3$ the optimal strategy can be established and on average 2 and $8/3$ steps are required respectively. There are many tantilizing variations on this problem, which we discuss with some conjectures.
back to list of papers
Here is a problem which I and a colleague formulated a few years ago. It occurred to me that it may be the sort of thing that people who read this newsgroup would enjoy thinking about. THE RENDEZVOUS PROBLEM Two people are lost from each other a maze of n rooms. How should they move around in order to minimize the expected time it will take for them to find one another? This is roughly the problem you face if you go to a shopping mall with a friend, become separated, and then wonder how to find your friend in minimal time, knowing that he may also be hunting for you. The problem arose through modelling issues that arise in synchonizing or de-sychonizing parallel processors performing a calculation. Suppose the n rooms are identical, unlabelled and there is no map that allows the players to break the symmetry of the set up. The travelling time between any two rooms is the same. Therefore, until such times as they meet, each of the two players must simply choose a room to visit at time t, as a function of the rooms he has visited at times 0,1,...,t-1, (this being information he can remember). Each player has his own personal labelling of the rooms. If one player stays still and the other tours the the rooms one by one in random order then the expected time is clearly n/2. But the two persons have no way of deciding which of them should stay still while the other searches. If they both search rooms at random, the expected meeting time is n. But is there some algorithm they can follow, which is symmetric with respect to the two people - (perhaps an algorithm which they both read in their copies of the Hitchhiker's Guide to the Galaxy) -, that guarantees an expected meeting time less than n? The rules of this problem are that the algorithm is not allowed to break symmetry by referring to some external information, such as saying `the older person should do X, while the younger does Y.' (The HHGTTG cannot rely on readers knowing such facts about one another.) Here is what is known an unknown about this problem: 1. The optimal algorithm for n=2 is known. The expected meeting time is 2. 2. The above paper claimed to have the optimal strategy for n=3, but an error was later found. It has taken 15 years to find a proof for n=3. See now weber-k3.pdf The optimal algorithm for n=4 and higher is not known. 3. There are algorithms that guarantee meeting in about 0.8n, but no knowledge of what is best, or whether something less than linear growth in n is possible. 4. Surprisingly, it has not been proved that the minimal expected meeting time is an increasing function of n. This appears harder to prove than you would first think! 5. If the players are allowed to leave complicated messages for each other behind in the rooms, they still cannot manage to meet in expected time less than a constant times sqrt(n). If they can leave messages behind, these message need be no more complicated that to simply say, "I was here", in order to realise an expected meeting time less than a constant time sqrt(n). 6. If the problem is modified so that players are not symmetric and they are therefore allowed to follow different algorithms, i.e., one is a child and the other a parent, then the optimal solution is for the child to stay still while the parent looks for her (taking n/2 steps on average). This is obvious, but a proof of optimality is harder than you might think. (I didn't intend to write so much about this problem, but I got carried away, thinking this might be an interesting problem for rec.puzzles or math.research, where I may post it.) Reference: Anderson, E.J. and Weber, R.R. (1990) The rendezvous problem on discrete locations", Journal of Applied Probability, 28, 839-851. +-------------------------+---------------------------------------------+ | Prof Richard R. Weber | Email: firstname.lastname@example.org | | Statistical Laboratory | Post: 16 Mill Lane, Cambridge, UK, CB2 1SB | | University of Cambridge | Tel: +44 223 337953 Fax: +44 223 337956 | +-------------------------+---------------------------------------------+