2014 USAMO Problems/Problem 4

Revision as of 17:13, 30 April 2014 by Suli (talk | contribs) (Solution)

Problem

Let $k$ be a positive integer. Two players $A$ and $B$ play a game on an infinite grid of regular hexagons. Initially all the grid cells are empty. Then the players alternately take turns with $A$ moving first. In his move, $A$ may choose two adjacent hexagons in the grid which are empty and place a counter in both of them. In his move, $B$ may choose any counter on the board and remove it. If at any time there are $k$ consecutive grid cells in a line all of which contain a counter, $A$ wins. Find the minimum value of $k$ for which $A$ cannot win in a finite number of moves, or prove that no such minimum value exists.

Solution

We claim that the minimum $k$ such that A cannot create a $k$ in a row is $\boxed{6}$.

It is easy to verify that player A can create a 5 in a row.

[Verification here]

Otherwise, tile the hexagon board in an A-B-C-A-B-C-A-B-C format. To prevent player A from obtaining a 6 in a row, all player B has to do is to remove counters placed on A by player A. Because no two A's are adjacent, player A can play at most one A at a time; thus, there can at most be one counter on an A tile at a time. Clearly, then, a 6 in a row, which requires A-B-C-A-B-C (or two A's), is then impossible, completing the proof.