2014 USAJMO Problems/Problem 5

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

The answer is $k=6$ . We prove that $A$ can win for $k=5$ (which hence proves it for $k<5$ as well) and show that $B$ can thwart $A$ for $k\geq 6$ .

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 $(0, 1)$ and $(1, 0)$ , respectively. Then, for example, the below-and-right hexagon touching the origin is $(1, -1)$ . So two hexagons touch if their coordinate difference is one of these.

Now for $k=5$ , person $A$ places his counters only in $\{0, 1, 2, 3, 4\}\times\{0, 1\}$ . Note that if, at $A$ 's turn, there are 4 counters in either column, then $A$ can win immediately, so let us assume that in both columns there are at least 2 missing, meaning that at most $6$ counters are on the board. We would like to find when $A$ cannot play under these circumstances. If we look at the disjoint sets

$\{(0, 0), (0, 1), (1, 0)\}, \{(1, 1), (2, 0), (2, 1)\}, \{(3, 0), (3, 1), (4, 0)\}, \{(4, 1)\}$

we see that either some set has at least $2$ hexagons without counters, in which case $A$ can move, or all four sets have exactly $1$ missing counter. Similarly for the sets

$\{(0, 0)\}, \{(0, 1), (1, 0), (1, 1)\}, \{(2, 0), (2, 1), (3, 0)\}, \{(3, 1), (4, 0), (4, 1)\}$

So both $(0, 0), (4, 1)$ have no token on them. This means that $(0, 1), (1, 0), (3, 1), (4, 0)$ do. Thus $(3, 0)$ and $(1, 1)$ do not. So this is the only situation in which $A$ can neither win immediately nor play in only these 10 hexagons.

So $A$ 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, $A$ plays in hexagons $(5, 0)$ and $(5, 1)$ . Then $B$ either removes $(5, 1)$ so that $A$ can win at $(2, 0)$ , or $B$ removes $(5, 0)$ and $A$ plays at $(5, 0)$ and $(4, 1)$ and then at either $(3, 0)$ or $(1, 1)$ the next turn, or $B$ removes one of $\{0, 1, 2, 3, 4\}\times\{0, 1\}$ in which case $A$ can either win immediately at $(3, 0)$ or can play in both columns, and then win the next turn.

Now if $k\geq 6$ , then if $A$ plays on anything in the lattice generated by $(2, -1)$ and $(1, 1)$ , that is $(2a+b, b-a)$ for $a, b$ integers, then $B$ removes it. Otherwise, $B$ removes any of $A$ 's counters. This works because in order for $A$ to win, there must be at least 2 counters in this lattice, but $A$ can only put a counter on $1$ at any time, so there's at most 1 on the lattice at any time.

So $A$ wins if $k\leq 5$ , and $B$ wins if $k\geq 6$ .

Page

Toolbox

Search

2014 USAJMO Problems/Problem 5

Problem

Solution