Two conjectures on rendezvous in K3
Steven Alpern, Gal Shmuel · London School of Economics and Political Science Research Online (London School of Economics and Political Science) · 2006
The symmetric rendezvous problem on the triangle K3 asks how two players, initially randomly placed at distinct vertices, can meet in the minimal expected number of steps v: They must follow a common mixed strategy, with independent randomization. This problem, posed by Alpern and …rst studied by Anderson and Weber [6] (see also [4],[3]) assumes they have no common notion of a clockwise direction around the triangle- if they do, then the resulting problem cc has a minimum meeting time w which cannot be larger than v: Despite their apparent simplicity, both problems and cc are open. However there are two widely held conjectures regarding them: AW (Anderson-Weber) conjecture The rendezvous value of is given by v = 5=2: This expected meeting time is obtained by the stay-search strategy of choosing, in each two-period interval, to either stay where you are for two periods (probability 1=3) or search the remaining two vertices in equiprobable order (probability 2=3). CC (Common-Clockwise) Conjecture Having a common notion of clockwise does not help, that is, w = v: The purpose of this short note is to show that the AW Conjecture implies the CC Conjecture. More generally, we establish an inequality between the two rendezvous values w and v: Theorem 1 v