Alice and Bob form a team to play a game. At the start of the game, the two of them are dropped at two positions on a train whose total length is kilometer. The train is enclosed and completely dark, so unless they are at the front or the rear of the train, they will not know their own position, nor can they know their teammate's position. The game equips each of them with a device, whose left half displays:
- the direction the holder is currently facing (so he/she can choose to move toward the front or the rear of the train);
- the total distance the holder has moved so far;
- whether the holder has currently touched the front of the train;
- whether the holder has currently touched the rear of the train.
The right half of the device displays the same information that appears on the left half of the teammate's device. The game ends the instant the two of them meet (i.e., their positions coincide).
Suppose that before the game begins, Alice and Bob are fully informed of the state of the train and all the functions of the devices, and that they are allowed to discuss their strategy together beforehand. Find the smallest real number such that there exists a strategy for Alice and Bob so that, no matter what positions the two of them are placed at when the game begins, they can guarantee that by the time the game ends, the sum of the distances the two of them have moved does not exceed kilometers.
Solution
Answer. .
- Construction: First, Alice walks toward the front of the train for kilometers. If Alice touches the front of the train, then Bob starts walking toward the front, so that before the two of them have walked a combined kilometers, they can be guaranteed to coincide. Suppose Alice does not touch the front; then it is Bob's turn to walk toward the front, until he either touches the front or meets Alice, and if he touches the front he turns back. Then before the two of them have walked a combined kilometers, they can be guaranteed to coincide.
- Lower bound: Define a person's exploration value as the distance between the rightmost point he has reached and the leftmost point he has reached. If the sum of the two people's exploration values is less than kilometer, then one can place the two people's explored intervals at disjoint positions on the train. Without loss of generality, suppose Alice is the first person whose exploration value reaches kilometers; then let him touch the front or the rear of the train at the very instant his exploration value reaches kilometers, and without loss of generality let him touch the front. Then one can place the rightmost point Bob has reached at a distance from the rear of the train. Suppose Bob's exploration value is ; then at this moment the distance between the two of them is kilometers, so in total the two of them must walk at least kilometers before they can meet each other. Since can be any arbitrarily small positive real number, they must walk at least kilometers in total to guarantee meeting each other.