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 "2021 USAMO Problems/Problem 3"

(list)
(Addition of solution 1)
Line 12: Line 12:
 
</asy>
 
</asy>
 
For which <math>n</math> is it possible that, after some non-zero number of moves, the board has no stones?
 
For which <math>n</math> is it possible that, after some non-zero number of moves, the board has no stones?
−
== Solution (WIP) ==
+
== Solution 1 ==
 +
 
 +
Label the bottom right cell as <math>\omega^0</math> where <math>\omega = e^{i2\pi/3}</math>. Then label each cell with <math>\omega^d</math> where <math>d</math> is the <i>Manhattan distance</i> of the current cell from the bottom right cell.
 +
 
 +
No matter where an L-shaped tromino is placed, the sum of the labels in the cells is,
 +
 
 +
<cmath>\omega^0 + \omega^1 + \omega^2 = \frac{\omega^3 - 1}{\omega - 1} = \frac{0}{\omega - 1} = 0</cmath>
 +
 
 +
If <math>n = 3k + 1</math>. Then the sum of all the labels in the cells in a row or column is,
 +
 
 +
<cmath>k(\omega^0 + \omega^1 + \omega^2)+\omega^0 = 1</cmath>
 +
 
 +
If <math>n = 3k + 2</math>. Then the sum of all the labels in cells in a row or column is,
 +
 
 +
<cmath>k(\omega^0 + \omega^1 + \omega^2) + \omega^0 + \omega^1 = 1 + \omega</cmath>
 +
 
 +
Let <math>S</math> be the sum of all the labels of cells containing a stone. In either above case, placing an L-shaped Tromino leaves <math>S</math> invariant but removing a row or column of stone causes <math>\textrm{Re}(S)</math> to decrease (by <math>1</math> or <math>1/2</math> in each case). However the empty grid has <math>S=0</math>, so this can't be reached.
 +
 
 +
Hence <math>n=3k</math>. We now provide a sequence of moves which empties the grid. Divide the grid into <math>3\times 3</math> grids and do the following to every sub-grid. <em>(When I refer to placing an L-shaped tromino on a cell, I am refering to the position of the bottom middle stone)</em>
 +
 
 +
<ul>
 +
<li>Add an L-shaped tromino to the bottom left cell and middle cell</li>
 +
<li>Remove the middle row</li>
 +
<li>Add an L-shaped tromino to the middle left cell</li>
 +
<li>Remove the left and middle columns</li>
 +
</ul>
 +
and we're done, the grid is empty!
 +
 
 +
<em>~PolyaMath</em>

Revision as of 12:46, 20 January 2025

Let $n \geq 2$ be an integer. An $n \times n$ board is initially empty. Each minute, you may perform one of three moves:

  • 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?

Solution 1

Label the bottom right cell as $\omega^0$ where $\omega = e^{i2\pi/3}$. Then label each cell with $\omega^d$ where $d$ is the Manhattan distance of the current cell from the bottom right cell.

No matter where an L-shaped tromino is placed, the sum of the labels in the cells is,

\[\omega^0 + \omega^1 + \omega^2 = \frac{\omega^3 - 1}{\omega - 1} = \frac{0}{\omega - 1} = 0\]

If $n = 3k + 1$. Then the sum of all the labels in the cells in a row or column is,

\[k(\omega^0 + \omega^1 + \omega^2)+\omega^0 = 1\]

If $n = 3k + 2$. Then the sum of all the labels in cells in a row or column is,

\[k(\omega^0 + \omega^1 + \omega^2) + \omega^0 + \omega^1 = 1 + \omega\]

Let $S$ be the sum of all the labels of cells containing a stone. In either above case, placing an L-shaped Tromino leaves $S$ invariant but removing a row or column of stone causes $\textrm{Re}(S)$ to decrease (by $1$ or $1/2$ in each case). However the empty grid has $S=0$, so this can't be reached.

Hence $n=3k$. We now provide a sequence of moves which empties the grid. Divide the grid into $3\times 3$ grids and do the following to every sub-grid. (When I refer to placing an L-shaped tromino on a cell, I am refering to the position of the bottom middle stone)

  • Add an L-shaped tromino to the bottom left cell and middle cell
  • Remove the middle row
  • Add an L-shaped tromino to the middle left cell
  • Remove the left and middle columns

and we're done, the grid is empty!

~PolyaMath

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_USAMO_Problems/Problem_3&oldid=240722"