Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2014 USAJMO Problems/Problem 5"

(Created page with "==Problem== Let <math>k</math> be a positive integer. Two players <math>A</math> and <math>B</math> play a game on an infinite grid of regular hexagons. Initially all the grid ce...")
 
 
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
 +
 +
The answer is <math>k=6</math>. We prove that <math>A</math> can win for <math>k=5</math> (which hence proves it for <math>k<5</math> as well) and show that <math>B</math> can thwart <math>A</math> for <math>k\geq 6</math>.
 +
 +
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 <math>(0, 1)</math> and <math>(1, 0)</math>, respectively. Then, for example, the below-and-right hexagon touching the origin is <math>(1, -1)</math>. So two hexagons touch if their coordinate difference is one of these.
 +
 +
Now for <math>k=5</math>, person <math>A</math> places his counters only in <math>\{0, 1, 2, 3, 4\}\times\{0, 1\}</math>. Note that if, at <math>A</math>'s turn, there are 4 counters in either column, then <math>A</math> can win immediately, so let us assume that in both columns there are at least 2 missing, meaning that at most <math>6</math> counters are on the board. We would like to find when <math>A</math> cannot play under these circumstances. If we look at the disjoint sets
 +
 +
<math>\{(0, 0), (0, 1), (1, 0)\}, \{(1, 1), (2, 0), (2, 1)\}, \{(3, 0), (3, 1), (4, 0)\}, \{(4, 1)\}</math>
 +
 +
we see that either some set has at least <math>2</math> hexagons without counters, in which case <math>A</math> can move, or all four sets have exactly <math>1</math> missing counter. Similarly for the sets
 +
 +
<math>\{(0, 0)\}, \{(0, 1), (1, 0), (1, 1)\}, \{(2, 0), (2, 1), (3, 0)\}, \{(3, 1), (4, 0), (4, 1)\}</math>
 +
 +
So both <math>(0, 0), (4, 1)</math> have no token on them. This means that <math>(0, 1), (1, 0), (3, 1), (4, 0)</math> do. Thus <math>(3, 0)</math> and <math>(1, 1)</math> do not. So this is the only situation in which <math>A</math> can neither win immediately nor play in only these 10 hexagons.
 +
 +
So <math>A</math> 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, <math>A</math> plays in hexagons <math>(5, 0)</math> and <math>(5, 1)</math>. Then <math>B</math> either removes <math>(5, 1)</math> so that <math>A</math> can win at <math>(2, 0)</math>, or <math>B</math> removes <math>(5, 0)</math> and <math>A</math> plays at <math>(5, 0)</math> and <math>(4, 1)</math> and then at either <math>(3, 0)</math> or <math>(1, 1)</math> the next turn, or <math>B</math> removes one of <math>\{0, 1, 2, 3, 4\}\times\{0, 1\}</math> in which case <math>A</math> can either win immediately at <math>(3, 0)</math> or can play in both columns, and then win the next turn.
 +
 +
Now if <math>k\geq 6</math>, then if <math>A</math> plays on anything in the lattice generated by <math>(2, -1)</math> and <math>(1, 1)</math>, that is <math>(2a+b, b-a)</math> for <math>a, b</math> integers, then <math>B</math> removes it. Otherwise, <math>B</math> removes any of <math>A</math>'s counters. This works because in order for <math>A</math> to win, there must be at least 2 counters in this lattice, but <math>A</math> can only put a counter on <math>1</math> at any time, so there's at most 1 on the lattice at any time.
 +
 +
So <math>A</math> wins if <math>k\leq 5</math>, and <math>B</math> wins if <math>k\geq 6</math>.

Latest revision as of 19:18, 18 April 2016

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$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2014_USAJMO_Problems/Problem_5&oldid=78124"