Centre for Discrete and Applicable Mathematics

 CDAM Research Report, LSE-CDAM-2006-21

December 2006

Two Conjectures on Rendezvous in K3

Steve Alpern and Shmuel Gal

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 as the 'telephone problem' and first studied by Anderson and Weber, assumes they have no common notion of a clockwise direction around the triangle - if they do, then the resulting 'common clockwise' problem has a minimum meeting time w which cannot be larger than v. This short note relates two conjectures about this problem, and briefly discusses a similar result for the symmetric rendezvous problem on the line - with and without a common sense of direction.

A PDF file (53 kB) with the full contents of this report can be downloaded by clicking here.

Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2006-21, together with your name and postal address to:
CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
Houghton Street
London WC2A 2AE, U.K.
Phone: +44(0)-20-7955 7494.
Fax: +44(0)-20-7955 6877.
Email: info@maths.lse.ac.uk 

Introduction to the CDAM Research Report Series.
CDAM Homepage.

Copyright © London School of Economics & Political Science 2006