University of Cambridge > Mathematics > Statistical Laboratory >
Richard Weber > Unsolved problems >  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 started in at time 0, and those he has
visited at times 1,...,t-1, (this b