Bela and Jenn play the following game on the closed interval of the real number line, where is a fixed integer greater than . They take turns playing, with Bela going first. At his first turn, Bela chooses any real number in the interval . Thereafter, the player whose turn it is chooses a real number that is more than one unit away from all numbers previously chosen by either player. A player unable to choose such a number loses. Using optimal strategy, which player will win the game?
- A)
- B)
- C)
- D)
- E)
Answer
A
Key insight
Bela takes the midpoint n/2 first, then mirrors every Jenn move across it; the mirror move is always legal, so Jenn runs out first.
Solution
Bela starts by choosing the midpoint . From then on, whenever Jenn chooses a number , Bela answers with its mirror image .
Why this is always legal: the set of chosen numbers is symmetric about after each of Bela's turns. If Jenn's is more than from every chosen number, then is more than from every chosen number as well (distances are preserved by reflection). And , since is already taken and any legal is more than away from it; also is not within of , because .
So Bela always has a move after Jenn does. The game ends (choices are spaced more than apart on a bounded interval, so only finitely many fit), and the player who first cannot move is necessarily Jenn.
The answer is
Why this works
Symmetry strategies win games where the board has a center: the first player occupies the center, then copies the opponent's move reflected through it. The proof has two parts, and both matter: the mirrored move is legal, and it never coincides with (or conflicts with) the move just made. The parity of is a distraction; the answer choices mentioning odd/even are bait.
The trap
Trying to analyze the count of remaining moves as a function of n (odd versus even) instead of looking for a strategy-stealing symmetry.
Common mistakes
- Trying to analyze the count of remaining moves as a function of n (odd versus even) instead of looking for a strategy-stealing symmetry.
- Believing Jenn can also mirror; she cannot, because the midpoint is already gone and the first player owns the symmetry.
Techniques
Exploit symmetry to reduce work or pair up objects