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 spaces 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 exists.
Solution:
The answer is . First we show that cannot win for . Color the grid in three colors so that no two adjacent spaces have the same color, and arbitrarily pick one color C. will play by always removing a counter from a space colored that just played. If there is no such counter, plays arbitrarily. Because cannot cover two spaces colored simultaneously, it is possible for to play in this fashion. Now note that any line of six consecutive squares contains two spaces colored . For to win he must cover both, but 's strategy ensures at most one space colored will have a counter at any time.
Now we show that can obtain 5 counters in a row. Take a set of cells in the grid forming the shape shown below. We will have play counters only in this set of grid cells until this is no longer possible. Since only removes one counter for every two places, the number of counters in this set will increase each turn, so at some point it will be impossible for to play in this set anymore. At that point any two adjacent grid spaces in the set have at least one counter between them.
Consider only the top row of cells in the set, and take the lengths of each consecutive run of cells. If there are two adjacent runs that have a combined length of at least 4 , then gets 5 counters in a row by filling the space in between. Otherwise, a bit of case analysis shows that there exists a run of 1 counter which is neither the first nor last run. This single counter has an empty space on either side of it on the first row. As a result, the four spaces of the second row touching these two empty spaces all must have counters. Then can play in the 5 th cell on either side of these 4 to get 5 counters in a row. So in all cases can win with .
This problem and solution was suggested by Palmer Mebane.
The problems on this page are the property of the MAA's American Mathematics Competitions