Maths Olympiad Prep

Library / /30 of 31

Combinatorics Difficulty 8.9 Shortlist Prove it Baltic Way

Olga and Sasha play a game on an infinite hexagonal grid. They take alternating turns in placing a counter on a free hexagon of their choice, with Olga opening the game. Beginning from the 2018th move, a new rule will come into play. A counter may now be placed only on those free hexagons having at least two occupied neighbours.
A player loses when she or he either is unable to make a turn, or has filled a pattern of the rhomboid shape below with counters (rotated in any possible way). Determine which player, if any, possesses a winning strategy.

Figure 1

Solution

Answer: Olga has a winning strategy.
The game cannot go on forever. Draw a large hexagon enclosing all 2017 counters in play after the 2017th move, as in Figure 1. While it will be possible to place future counters in the hexagonal frame at distance 1 from the shaded part (i.e. immediately surrounding it), where DD and EE are located, it will be impossible to reach cells at distance 2 from the shaded part, where FF is located. Indeed, in order to place a counter at FF, first counters must be placed on cells DD and EE.

Figure 2

Figure 1: A large shaded hexagon enclosing all 2017 counters in play after the 2017th move.
Assume that the cells E1,E2,,EnE_1, E_2, \dots, E_n to the right of EE contain counters, but the next cell to the right is En+1E_{n+1} and it is empty. Observe that the counter on En1E_{n-1} has been placed before the counter on EnE_n, because otherwise the forbidden rhombus is formed by the cells En1,EnE_{n-1}, E_n and two ancestors of EnE_n in the previous row. By analogous reasoning considering the moment of placing the counter on En1E_{n-1} one can prove that the counter on En2E_{n-2} has been placed before the counter on En1E_{n-1}, etc. Thus we conclude that the counter on DD has been placed before the counter on EE. But changing the direction of our reasoning to the left we similarly conclude that counter on EE has been placed before the counter on DD. A contradiction.

Now, let Olga place her first counter in any hexagon HH, and then respond to each of Sasha's successive moves by symmetry, choosing to place her counter on the reflexion in HH of his chosen hexagon (in other words, diametrically opposite to his with respect to HH). It is clear that the gameplay will be completely symmetrical after each of Olga's moves. Hence she may respond, even under the additional rule, to any move Sasha might make. It is also evident that she will never complete a forbidden rhombus if Sasha did not already do so before. Hence Olga is always certain to have a legal move at her disposal, and so will eventually win.

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 and solution reproduced as published; topic and difficulty added by this site.