Difference between revisions of "2021 USAMO Problems/Problem 3"

(4 intermediate revisions by the same user not shown)
Line 1: Line 1:
The 2021 USAMO has not been out yet. Please do not edit this page. If you are a site admin, please delete this page.
+
Let <math>n \geq 2</math> be an integer. An <math>n \times n</math> board is initially empty. Each minute, you may perform one of three moves:
 +
[list]
 +
[*] If there is an L-shaped tromino region of three cells without stones on the board (see figure; rotations not allowed), you may place a stone in each of those cells.
 +
[*] If all cells in a column have a stone, you may remove all stones from that column.
 +
[*] If all cells in a row have a stone, you may remove all stones from that row.
 +
<asy>
 +
unitsize(20);
 +
draw((0,0)--(4,0)--(4,4)--(0,4)--(0,0));
 +
fill((0.2,3.8)--(1.8,3.8)--(1.8, 1.8)--(3.8, 1.8)--(3.8, 0.2)--(0.2, 0.2)--cycle, grey);
 +
draw((0.2,3.8)--(1.8,3.8)--(1.8, 1.8)--(3.8, 1.8)--(3.8, 0.2)--(0.2, 0.2)--(0.2, 3.8), linewidth(2));
 +
draw((0,2)--(4,2));
 +
draw((2,4)--(2,0));
 +
</asy>
 +
For which <math>n</math> is it possible that, after some non-zero number of moves, the board has no stones?

Revision as of 07:21, 18 July 2021

Let $n \geq 2$ be an integer. An $n \times n$ board is initially empty. Each minute, you may perform one of three moves: [list] [*] If there is an L-shaped tromino region of three cells without stones on the board (see figure; rotations not allowed), you may place a stone in each of those cells. [*] If all cells in a column have a stone, you may remove all stones from that column. [*] If all cells in a row have a stone, you may remove all stones from that row. [asy] unitsize(20); draw((0,0)--(4,0)--(4,4)--(0,4)--(0,0)); fill((0.2,3.8)--(1.8,3.8)--(1.8, 1.8)--(3.8, 1.8)--(3.8, 0.2)--(0.2, 0.2)--cycle, grey); draw((0.2,3.8)--(1.8,3.8)--(1.8, 1.8)--(3.8, 1.8)--(3.8, 0.2)--(0.2, 0.2)--(0.2, 3.8), linewidth(2)); draw((0,2)--(4,2)); draw((2,4)--(2,0)); [/asy] For which $n$ is it possible that, after some non-zero number of moves, the board has no stones?