2014 USAJMO Problems/Problem 5
Problem
Let be a positive integer. Two players and play a game on an infinite grid of regular hexagons. Initially all the grid cells are empty. Then the players alternately take turns with moving first. In his move, may choose two adjacent hexagons in the grid which are empty and place a counter in both of them. In his move, may choose any counter on the board and remove it. If at any time there are consecutive grid cells in a line all of which contain a counter, wins. Find the minimum value of for which cannot win in a finite number of moves, or prove that no such minimum value exists.
Solution
The answer is . We prove that can win for (which hence proves it for as well) and show that can thwart for .
Arrange the board so that a pair of opposite sides are horizontal. Create a coordinate system on the board by setting the center of some hexagon as the origin and setting the hexagons directly above and above-and-right as and , respectively. Then, for example, the below-and-right hexagon touching the origin is . So two hexagons touch if their coordinate difference is one of these.
Now for , person places his counters only in . Note that if, at 's turn, there are 4 counters in either column, then can win immediately, so let us assume that in both columns there are at least 2 missing, meaning that at most counters are on the board. We would like to find when cannot play under these circumstances. If we look at the disjoint sets
we see that either some set has at least hexagons without counters, in which case can move, or all four sets have exactly missing counter. Similarly for the sets
So both have no token on them. This means that do. Thus and do not. So this is the only situation in which can neither win immediately nor play in only these 10 hexagons.
So plays only in these 10 hexagons until either he has a win or he can't anymore. If he wins, then we're done. Otherwise, plays in hexagons and . Then either removes so that can win at , or removes and plays at and and then at either or the next turn, or removes one of in which case can either win immediately at or can play in both columns, and then win the next turn.
Now if , then if plays on anything in the lattice generated by and , that is for integers, then removes it. Otherwise, removes any of 's counters. This works because in order for to win, there must be at least 2 counters in this lattice, but can only put a counter on at any time, so there's at most 1 on the lattice at any time.
So wins if , and wins if .