Difference between revisions of "2014 USAMO Problems/Problem 4"
(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...") |
(→Solution) |
||
| Line 3: | Line 3: | ||
==Solution== | ==Solution== | ||
| + | We claim that the minimum <math>k</math> such that A cannot create a <math>k</math> in a row is <math>\boxed{6}</math>. | ||
| + | |||
| + | 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. | ||
Revision as of 18:13, 30 April 2014
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
We claim that the minimum such that A cannot create a in a row is 
.
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.
