Two people are lost and trying to find each other. There are n locations. Each step, each person picks a location. They follow the same randomized strategy — no coordination, no asymmetry. The question: how fast can they expect to meet?

Anderson and Weber proposed a strategy in 1990: with some probability, stay at one location for n-1 steps; otherwise, visit all other locations in random order. For 2 locations, this is optimal. For 3 locations, also optimal. For 36 years, the question of whether it was optimal for n ≥ 4 remained open or only partially resolved.

Cembrano, Fischer, and Klimm prove it’s suboptimal for all n ≥ 4. The strategy that works perfectly when there are few choices fails when the space grows. The geometric structure of the problem changes at n = 4 in a way that makes the wait-or-tour approach suboptimal.

The structural point: symmetric strategies that are optimal in small spaces are not guaranteed to scale. The rendezvous problem is maximally constrained — both players must use identical strategies, so there’s no room for role differentiation. Within that constraint, the optimal behavior depends on the size of the search space. What works at n = 3 doesn’t work at n = 4 because the number of possible configurations crosses a threshold where the stay-or-tour dichotomy is no longer fine-grained enough to exploit the combinatorial structure.

Small-space optimality is not evidence of general optimality. The boundary where simple strategies break is often exact — not a gradual degradation but a clean transition at a specific problem size.