Maths Olympiad Prep

Library / /101 of 105

Combinatorics Difficulty 5.7 AIME, harder Prove it United States

Problem:

Two players play a game with pennies, which are circles of radius 11, on an m×nm \times n rectangular table. Each player takes turns putting a penny on the table so that it touches no other penny. The first player who is unable to do so loses. The table starts with no pennies on it. Assuming that there is an infinite supply of pennies, for what values of mm and nn does the first player have a winning strategy?

Solution

Solution:

If m<2m<2 or n<2n<2, then it is not possible to fit even one penny on the table, so the first player loses immediately. On the other hand, if m2m \geq 2 and n2n \geq 2, we will show that the first player can win. Let OO denote the center of the table, and let the first player place his first penny so that it is centered at OO. The resulting configuration is centrally symmetric (i.e. it remains the same under a rotation of 180180^{\circ} about OO). Now, whenever the second player places a penny with some center AA, the first player should respond with a penny centered at BB, the 180180^{\circ} rotation of AA about OO. It is evident that the first player always leaves a centrally symmetric configuration; we must show that this move is actually legal.

Since placing the penny with center AA was legal, the symmetry of the previous configuration means that, before this penny was placed, a move centered at BB was also legal. So, after the second player's move at AA, the first player can still legally move at BB unless the penny centered at BB intersects the penny centered at AA. If PP is an intersection point, then AP1AP \leq 1 and PB1PB \leq 1, so AB2AB \leq 2. But OO is the midpoint of ABAB, so AO=AB/21AO = AB / 2 \leq 1. This means that AA lies inside the penny placed with center OO; this is a contradiction. Hence, the move with center BB is, in fact, legal.

Thus, the first player can always legally move so as to preserve central symmetry. This move's availability means that the first player never loses. But since only a finite number of pennies can be placed without overlap, the game eventually ends, and it is the second player who loses.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.