2021 USAMO Problems/Problem 3: Difference between revisions
No edit summary |
|||
| (8 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
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: | 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: | ||
*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); | unitsize(20); | ||
draw((0,0)--(4,0)--(4,4)--(0,4)--(0,0)); | draw((0,0)--(4,0)--(4,4)--(0,4)--(0,0)); | ||
| Line 12: | Line 10: | ||
draw((0,2)--(4,2)); | draw((0,2)--(4,2)); | ||
draw((2,4)--(2,0)); | 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? | For which <math>n</math> is it possible that, after some non-zero number of moves, the board has no stones? | ||
== 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 left 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 | |||
Latest revision as of 12:54, 20 January 2025
Let 
be an integer. An 
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]](http://latex.artofproblemsolving.com/0/7/1/071cfa01f4b3baffd591a2e465d1f3ecfbc58046.png)
For which 
is it possible that, after some non-zero number of moves, the board has no stones?
Solution 1
Label the bottom right cell as 
where 
. Then label each cell with 
where 
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\]](http://latex.artofproblemsolving.com/f/d/e/fded5e2d32436ddedb3bb14d950af87a6e618175.png)
If 
. 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\]](http://latex.artofproblemsolving.com/4/2/0/4208bb1edd298df375f3839b25d81a6ff1a3b8ce.png)
If 
. 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\]](http://latex.artofproblemsolving.com/0/4/7/047d7a9542dbe46fb626ad74c7ca1ac735586d21.png)
Let 
be the sum of all the labels of cells containing a stone. In either above case, placing an L-shaped Tromino leaves invariant but removing a row or column of stone causes 
to decrease (by 
or 
in each case). However the empty grid has 
, so this can't be reached.
Hence 
. We now provide a sequence of moves which empties the grid. Divide the grid into 
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 left 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
