The Rendezvous Problem is a logical dilemma originally formulated by Steve Alpern in 1976. Two people are lost in a location with n rooms. How should they move around to find each other in minimum time?
Obviously, they have no cell phone to communicate (it’s 1976). The n rooms are identical and unlabelled, and the travelling time between any two rooms is the same.
If both stay still, they will never meet. If both move randomly, they may take longer to meet (the expected meeting time = n). If one of them stays and the other moves, the meeting time reduces to n/2, but there is no way to decide who to move and who remains still.
Anderson and Weber proposed a probabilistic solution in which each person, after each step, either stays at her current location with probability p or moves randomly with probability 1-p until the two meet. They estimated p = 1/2 for n = 2 and p = 1/3 for n = 3. When n is large, p becomes 0.2475; the expected meeting time is ca. 0.8289n steps.
Rendezvous problem: Wiki
The rendezvous problem on discrete locations: Anderson and Weber
