The answer is $3 \mid n$. The construction it to divide the board into $3 \times 3$ squares, and in each, place a tromino (whose bottom left square is at) the bottom left and center. Then, delete all columns, and fill in some dominoes to get only rows left. Then delete all rows to win. For $3 \nmid n$, we weight the board using general weights $a, b$, such that entry $(m, n)$ is weighted $a^mb^n$ where the bottom left is $(0, 0)$ and the top right is $(n-1, n-1)$. Deleting a column (say, column $k$) is the same as subtracting\[a^k(1 + b + \ldots + b^{n-1})\]from the sum of total weights of cells with stones. Similarly, deleting row $k$ is the same as subtracting\[b^k(1 + a + \ldots + a^{n-1})\]from the sum of total weights of cells with stones. Adding a $L$-tromino with bottom left square in any of the bottom left $(n-1)^2$ squares, say $(m, n)$, adds $(1 + a + b)a^mb^n$. In the end, there are no stones, hence total weight $0$, thus, for any choice of weights,\[(1 + a + b)P(a, b) = (1 + b + \ldots + b^{n-1})Q(a) + (1 + a + \ldots + a^{n-1})R(b)\]for some polynomials $P, Q, R$ where $Q, R$ are single variable with degree at most $n$, and $P(a, b)$ is multivariable with $a$ degree $\leq n-1$ and $b$ degree also $\leq n-1$. Let $\omega$ be a fixed $n$th root of unity. Then any $(\omega^r, \omega^s)$ where $r, s \in [0, n-1]$. pushes the RHS to $0$. Furthermore, if $1 + x + y = 0$, then $x, y$ must be unit vectors that are the sides of an equilateral triangle, impossible if $3 \nmid n$. Hence, $P(a, b) = 0$ for $n^2$ distinct pairs $(a, b)$. Since $a, b$ both have degree $\leq n-1$, this should be sufficient to show $P$ is $0$ everywhere, meaning that no moves could have been made. If i botched the last part, how many points will I get docked ?

redacted; can't see figure

sdpandit wrote: I didn't qualify, but I don't think @above is correct - for example, $n=2$ works because you can fill any three cells, remove two of them, fill the remaining three, then remove all of them. You can't rotate the tromino

@above no rotations edit: sniped

@above n=2 does not work (you cannot rotate the L-shape)

You can't do that because you can't rotate the tromino, so only one L-shaped configuration can be filled. In the end, you are left with one filled square and no way to put any new trominos. Edit: triple sniped

[asy][asy] //made by bobthegod78 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][/asy]

This is bootleg tetris > Does anyone know if a weighting argument like $a^i b^j$ is worth any points (if I didn't finish the problem)? Probably not but maybe

^^ if you did it with general weights, its definitely >= 1

Mom can we have Tetris? Mom: We have Tetris at home. Tetris at home:

How much points would you get for guessing 3|n is the answer then showing all 3|n works?

We claim that only $3|n$ works. The construction for $n=3$ is trivial. To construct for $n=3k$, divide the $n\times n$ into $k^2$ $3\times 3$s and repeat the construction for $n=3$ on each one at the same time. It is easy to see that this works. Now, suppose that there exists a valid process of moves on an $n\times n$, and consdider adding every $L$ that was used in the process at the same time to the board. Then, each square will be hit, say $x_{i,j}$ times by $L$s. If row $i$ was operated on $r_i$ times and column $j$ was operated on $c_j$ times, then we have $x_{i,j}=r_i+c_j$. Obviously, $x_{n,n}=0$, so $c_n=0$. Thus, $x_{i,n}=r_i$. Now, the only way to touch square $(i,n)$ is with an $L$ at $(i,n-1)$. So, this tells us that $r_i$ Ls are at $(i,n-1)\forall i$. We now induct backwards to find out how many $L$s are on $(i,n-k)\forall k$. For convenience, denote the number of $L$s on $(i,j)$ as $k_{i,j}$. Associate $k_{i,j}$ with a vector $\vec{v}_{i,j}=\begin{bmatrix}a_1\\ a_2\\\vdots\\ a_{n-1}\end{bmatrix}$ such that $k_{i,j}=a_1r_1+\ldots + a_{n-1}r_{n-1}$. Also, associate column $n-1-d$ with a matrix $A_d=\begin{bmatrix}\vec{v}_{1,n-1-d}&\vec{v}_{2,n-1-d}&\cdots & \vec{v}_{n-1,n-1-d}\end{bmatrix}$. So, we have that $A_0=I_{n-1}$. Now, for column $d$, $(n,d)$ can only be accessed by $L$s at $(n-1,d)$, so $c_d=k_{n-1,d}$. This means that we have $$k_{i,d-1}=x_{i,d}-(k_{i,d}+k_{i-1,d})=r_i+k_{n-1,d}-(k_{i,d}+k_{i-1,d}$$Writing this in terms of our matrices, we get $$A_{n-d}=I_{n-1}+A_{n-d-1}\begin{bmatrix}0&0&\cdots &0\\\vdots\\0&0&\cdots &0\\1&1&\cdots &1\end{bmatrix}-A_{n-d-1}\begin{bmatrix}1&1&0&\cdots&0\\0&1&1&\cdots\\\vdots&&\ddots\\0&\cdots&0&1&1\end{bmatrix}$$So, $A_{d+1}=I+A_d\cdot K$, where $K=\begin{bmatrix}-1&-1&0&\cdots&0\\0&-1&-1&\cdots\\\vdots&&\ddots\\0&\cdots&-1&-1&0\\1&\cdots&1&1&0\end{bmatrix}$. Now, if $(r_1,\ldots,r_{n-1})$ produces a valid set of moves, this means that we should be done after all the $L$s are placed in column $1$. In particular, the recursion should give that no $L$s need to be placed in row $0$, corresponding to $A_{n-1}$. Hence, we get $\begin{bmatrix}r_1&r_2&\cdots&r_{n-1}\end{bmatrix}A_{n-1}=\begin{bmatrix}0&0&\cdots&0\end{bmatrix}$, which implies $\det(A_{n-1})=0$, as it has non-empty kernel. Claim: The eigenvalues of $K$ are $-(1+\omega^d)$ for $1\le d<n$, where $\omega=e^{\frac{2i\pi}{n}}$. Proof: We have that $\lambda I-K=\begin{bmatrix}\lambda+1&1&0&\cdots&0\\0&\lambda+1&1&\cdots\\\vdots&&\ddots\\0&\cdots&\lambda+1&1&0\\-1&\cdots&-1&-1&\lambda\end{bmatrix}$. Now, when we choose a set of $n$ entries to multiply for a term of the determinant, we should have them all nonzero and from different columns and rows. If the $1$ is chosen in row $i$, then we must choose the $1$ in row $i+1$ and so forth. So, all products can be characterized by taking $\lambda+1$ up to row $r$, and then all $1$s afterwards until the last row, where the choice is forced. This gives $n-1$ terms: \begin{align*}\det(\lambda I-K)&=\lambda(\lambda+1)^{n-2}+(\lambda+1)^{n-3}-(\lambda+1)^{n-4}+\ldots\\&= (1+\lambda)^{n-1}-(1+\lambda)^{n-2}+\ldots\\&= \pm\frac{(-1-\lambda)^n-1}{(-1-\lambda)-1}=0\end{align*}Hence, $\lambda$ is an eigenvalue iff $-1-\lambda=\omega^d\implies \lambda=-(1+\omega^d)$, as desired. Now, as $\lambda\neq 1$ for all $d$, $1$ is not an eigenvalue and $\det(K-I)\neq 0$. Recall that we want to show $\det(A_{n-1})=\det(K^{n-1}+K^{n-2}+\ldots+I)=0$, so it suffices to show $\det((K^{n-1}+\ldots+I)(K-I))=\det(K^n-I)=0$, or equivalently that $1$ is an eigenvalue of $K^n$. The eigenvalues of $K^n$ are just $n$th powers of those of $K$, so if this is true then we must have $-(1+\omega^a)=\omega^b$ for some $a,b$. However, this implies that $Re(\omega^a)=Re(\omega^b)=-1/2$, and they are primitive 3rd roots of unity, meaning $3|n$, as desired.

jj_ca888 wrote: \[(1 + a + b)P(a, b) = (1 + b + \ldots + b^{n-1})Q(a) + (1 + a + \ldots + a^{n-1})R(b)\]for some polynomials $P, Q, R$ where $Q, R$ are single variable with degree at most $n$, and $P(a, b)$ is multivariable with $a$ degree $\leq n-1$ and $b$ degree also $\leq n-1$. Wouldn't the degree of $P$ be at most $n-2$ (and the degree of $Q$ and $R$ are both at most $n-1$)? The maximal $a$-degree of any square in the board is $n-1$ since it's labeled from $0$ to $n-1$ and similarly for $b$. After you get this you can just plug in $b = -a-1$ and note that $\frac{b^n - 1}{b - 1}$ and $\frac{a^n - 1}{a-1}$ are coprime polynomials (after expanding $\frac{b^n - 1}{b - 1}$ in terms of $a$) since $n$ is not a multiple of $3$. That means $Q$ is a multiple of $\frac{a^n - 1}{a-1}$ (and by degree argument it's a constant times this polynomial) and similarly $R$ is a constant times $\frac{b^n-1}{b-1}$. Then there is no way for the right side to be a multiple of $a+b+1$, contradiction.

Oops, looks like i botched the end a bit more that I thought I did. How many points?

Quote: Hence, $P(a, b) = 0$ for $n^2$ distinct pairs $(a, b)$. Since $a, b$ both have degree $\leq n-1$, this should be sufficient to show $P$ is $0$ everywhere, meaning that no moves could have been made. Also I don't think this part is true, since for example if $P(a,b) = a + b$ and you have $n^2$ distinct pairs of the form $(x,-x)$ then you would get $n^2$ distinct pairs where $P(a,b) = 0$ which doesn't imply $P(a,b)$ is identically $0$. To patch that finish it looks like the actual choice of the points that you plug in matters and I'm not sure how to finish that way, but setting up the polynomial argument seems pretty significant.

Ok; i did write $P(w^r, b) = Q(b)$ has degree $n-1$ and $n$ distinct roots (wrong, turns out its $n-1$ and $n$ respectively, but this doesnt do anything to the ofllowing argument), proving $P(w^r, anything) = 0$. This basically finishes as $P(y, x) = P_x(y)$ has deg $<= n-1$ and $n$ roots, so is $0$ everywhere, for any $x$ is $0$, thus $P(anything, x) = 0$ for every $x$, hence $P(anything, anything) = 0$.

How many points for conjecturing that the answer is only 3|n and showing that it always works for 3|n?

jj_ca888 wrote: The answer is $3 \mid n$. The construction it to divide the board into $3 \times 3$ squares, and in each, place a tromino (whose bottom left square is at) the bottom left and center. Then, delete all columns, and fill in some dominoes to get only rows left. Then delete all rows to win. For $3 \nmid n$, we weight the board using general weights $a, b$, such that entry $(m, n)$ is weighted $a^mb^n$ where the bottom left is $(0, 0)$ and the top right is $(n-1, n-1)$. Deleting a column (say, column $k$) is the same as subtracting\[a^k(1 + b + \ldots + b^{n-1})\]from the sum of total weights of cells with stones. Similarly, deleting row $k$ is the same as subtracting\[b^k(1 + a + \ldots + a^{n-1})\]from the sum of total weights of cells with stones. Adding a $L$-tromino with bottom left square in any of the bottom left $(n-1)^2$ squares, say $(m, n)$, adds $(1 + a + b)a^mb^n$. In the end, there are no stones, hence total weight $0$, thus, for any choice of weights,\[(1 + a + b)P(a, b) = (1 + b + \ldots + b^{n-1})Q(a) + (1 + a + \ldots + a^{n-1})R(b)\]for some polynomials $P, Q, R$ where $Q, R$ are single variable with degree at most $n$, and $P(a, b)$ is multivariable with $a$ degree $\leq n-1$ and $b$ degree also $\leq n-1$. Let $\omega$ be a fixed $n$th root of unity. Then any $(\omega^r, \omega^s)$ where $r, s \in [0, n-1]$. pushes the RHS to $0$. Furthermore, if $1 + x + y = 0$, then $x, y$ must be unit vectors that are the sides of an equilateral triangle, impossible if $3 \nmid n$. Hence, $P(a, b) = 0$ for $n^2$ distinct pairs $(a, b)$. Since $a, b$ both have degree $\leq n-1$, this should be sufficient to show $P$ is $0$ everywhere, meaning that no moves could have been made. If I botched the last part, how many points will I get docked? Here's a possible finish.

how many points for $3|n$, construction, possible outline that used some weird casework bash and parity arguments?

The answer is $3\mid n$ Construction: For each 3x3 square, we have 010 111 110 Then 010 000 110 Then 110 110 110 Finally 000 000 000 Now I claim they're the only ones. Assign $x^{c-1}y^{r-1}$ to the intersection between the $c$th column from the right, and the $r$th row from the top. I contend that it is impossible to place a bunch of trinominoes, and remove one cell from each row and each col, and get an empty board. Suppose I remove $a_{i-1}$ stones from column $i$ and $b_{i-1}$ stones from row $i$ (note top row and rightmost col have 0 removals, as the top right corner would never get a stone), then I want $$xy+x+y\mid (\sum\limits_{i=1}^{n-1} a_iy^i)\frac{x^n-1}{x-1} + (\sum\limits_{i=1}^{n-1} b_ix^i)\frac{y^n-1}{y-1}$$ We wish to find $x,y$ st $xy+x+y=0$ while RHS$\ne 0$ Let $x^n=1, x\ne 1, y=\frac{1}{x+1}-1$, then I want $0=\left(\sum\limits_{i=1}^{n-1} b_ix^i \right) \frac{y^n-1}{y-1}$ Since $y\ne 1, x\ne 0, 0=\left(\sum\limits_{i=0}^{n-2} b_{i+1}x^i\right) ((\frac{-x}{x+1})^n-1)$ If $(\frac{-x}{x+1})^n-1=0, |x|=|x+1|=1$, so $x=\omega_3$. If $3\nmid n, (\frac{-x}{x+1})^n-1\ne 0$ when $x$ is an $n$th root of unity, so $\sum\limits_{i=0}^{n-2} b_{i+1}x^i$ has $n-1$ roots and thus $b_i=0\forall i$. Similarly, $a_i=0\forall i$, so this means if we place a bunch of trinominoes and remove a stone in each row or column, and reach an empty board, we've done nothing.

Quote: Hence, $P(a, b) = 0$ for $n^2$ distinct pairs $(a, b)$. Since $a, b$ both have degree $\leq n-1$, this should be sufficient to show $P$ is $0$ everywhere, meaning that no moves could have been made. Quote: Also I don't think this part is true, since for example if $P(a,b) = a + b$ and you have $n^2$ distinct pairs of the form $(x,-x)$ then you would get $n^2$ distinct pairs where $P(a,b) = 0$ which doesn't imply $P(a,b)$ is identically $0$. To patch that finish it looks like the actual choice of the points that you plug in matters and I'm not sure how to finish that way, but setting up the polynomial argument seems pretty significant. You can just finish using a weaker form of combinatorial nullstellensatz: $P(x,y)$ has degree at most $n-2$ in either variable, and $P(x,y) = 0$ for all $x,y \in S = \{e^{2\pi i k/n} \mid k=1,\dots,n-1\}$. Suppose $P(x,y) = \sum_{k\ge 0} P_k(x)y^k$, and fix any choice of $x\in S$, then $P$ (which becomes a polynomial in $y$) has degree at most $n-2$ and is zero for $n-1$ distinct values of $y$, and therefore is identically zero. So any $P_k(x)$ is zero for $n-1$ distinct choices of $x$, but $P_k(x)$ also has degree at most $n-2$, so they are all identically zero.

Nice problem! Haven't seen fake combo for a while in math contests. The answer is $3\mid n$. We obviously split the solution into two parts. Construction for $3\mid n$ I will just give the example when $n=12$, which easily generalizes. [asy][asy] size(5.5cm,0); int n = 12, i,j; pen p; label("Step 1",(6,12),N); for(i=0; i<=n; ++i){ p = heavygray; if(i % 3 == 0){ p = linewidth(1); } draw((0,i)--(n,i),p); draw((i,0)--(i,n),p); } void circ(int x, int y){ fill(circle((x+0.5,y+0.5),0.2),p); } for(i=0; i<12; i+=3){ for(j=0; j<12; j+=3){ p = red; circ(i,j);circ(i,j+1);circ(i+1,j); p = blue; circ(i+1,j+1);circ(i+2,j+1);circ(i+1,j+2); draw(shift(i+0.5,j+0.5)*((1,0)--(0,0)--(0,1)),red); draw(shift(i+1.5,j+1.5)*((1,0)--(0,0)--(0,1)),blue); } } [/asy][/asy] [asy][asy] size(5.5cm,0); int n = 12, i,j; pen p; label("Step 2",(6,12),N); for(i=0; i<=n; ++i){ p = heavygray; if(i % 3 == 0){ p = linewidth(1); } draw((0,i)--(n,i),p); draw((i,0)--(i,n),p); } void circ(int x, int y){ fill(circle((x+0.5,y+0.5),0.2),p); } for(i=0; i<12; i+=3){ for(j=0; j<12; j+=3){ p = red; circ(i,j);circ(i,j+1); p = blue; circ(i+2,j+1); } } [/asy][/asy] [asy][asy] size(5.5cm,0); int n = 12, i,j; pen p; label("Step 3",(6,12),N); for(i=0; i<=n; ++i){ p = heavygray; if(i % 3 == 0){ p = linewidth(1); } draw((0,i)--(n,i),p); draw((i,0)--(i,n),p); } void circ(int x, int y){ fill(circle((x+0.5,y+0.5),0.2),p); } for(i=0; i<12; i+=3){ for(j=0; j<12; j+=3){ p = red; circ(i,j);circ(i,j+1); p = blue; circ(i+2,j+1); p = deepgreen; circ(i+1,j); circ(i+2,j); circ(i+1,j+1); draw(shift(i+1.5,j+0.5)*((1,0)--(0,0)--(0,1)),deepgreen); } } [/asy][/asy] Proof for $3\nmid n$ We will use generating function. Let $a_{k-1}$ be the number of times we remove the $k$-th column from the left, and let $b_{k-1}$ be the number of times we remove the $k$-th row from the bottom. Observe that $a_{n-1}=b_{n-1}=0$. Define the polynomials $$P(x) = \sum_{k=0}^{n-1}a_kx^k\text{ and }Q(x) = \sum_{k=0}^{n-1} b_kx^k;$$so we have $\deg P, \deg Q \leq n-2$. If $c(k,\ell)$ denote the number of stones that have ever placed on the cell $(k+1,\ell+1)$, then \begin{align*}\sum_{k=0}^{n-1}\sum_{\ell=0}^{n-1} c(k,\ell)x^ky^{\ell} &= P(x)(1+y+y^2+\hdots+y^{n-1}) + Q(y)(1+x+x^2+\hdots+x^{n-1}) \\ &= P(x)\cdot\frac{y^n-1}{y-1} + Q(y)\cdot\frac{x^n-1}{x-1}. \end{align*}This polynomial must be divisible by $x+y+1$ due to the problem's condition. Thus, we get that by plugging in $y=-x-1$, $$P(x)\cdot\frac{(-x-1)^n-1}{-(x+2)} + Q(-(x+1))\cdot\frac{x^n-1}{x-1} = 0.$$However, we claim that $x^n-1$ and $(-x-1)^n-1$ are coprime polynomials in $\mathbb{Z}[x]$ (of course unless $3\nmid n$). Indeed, if $\alpha$ be the common root, then $|\alpha| = 1$ and $|-\alpha-1|=1$, which forces $\alpha^3=1$ or $3\mid n$. This gives the desired conclusion as $\deg P, \deg Q\leq n-2$.

Oops I thought that this was the third hardest problem (only) on this test. Am I crazy? We claim the answer is $3\mid n$. For $n=3$, we show a 4-step process: [asy][asy] size(20cm); filldraw((0,0)--(1,0)--(1,1)--(0,1)--cycle,red*0.2+white); filldraw((0,1)--(1,1)--(1,2)--(0,2)--cycle,red*0.2+white); filldraw((1,0)--(2,0)--(2,1)--(1,1)--cycle,red*0.2+white); filldraw((1,1)--(2,1)--(2,2)--(1,2)--cycle,green*0.2+white); filldraw((1,2)--(2,2)--(2,3)--(1,3)--cycle,green*0.2+white); filldraw((2,1)--(3,1)--(3,2)--(2,2)--cycle,green*0.2+white); for (int i=0;i<=3;++i) { draw((i,0)--(i,3)); } for (int i=0;i<=3;++i) { draw((0,i)--(3,i)); } filldraw((4,0)--(5,0)--(5,1)--(4,1)--cycle,red*0.2+white); filldraw((5,0)--(6,0)--(6,1)--(5,1)--cycle,red*0.2+white); filldraw((5,2)--(6,2)--(6,3)--(5,3)--cycle,green*0.2+white); for (int i=0;i<=3;++i) { draw((i+4,0)--(i+4,3)); } for (int i=0;i<=3;++i) { draw((4,i)--(7,i)); } filldraw((8,0)--(9,0)--(9,1)--(8,1)--cycle,red*0.2+white); filldraw((9,0)--(10,0)--(10,1)--(9,1)--cycle,red*0.2+white); filldraw((9,2)--(10,2)--(10,3)--(9,3)--cycle,green*0.2+white); filldraw((8,2)--(9,2)--(9,3)--(8,3)--cycle,blue*0.2+white); filldraw((8,1)--(9,1)--(9,2)--(8,2)--cycle,blue*0.2+white); filldraw((9,1)--(10,1)--(10,2)--(9,2)--cycle,blue*0.2+white); for (int i=0;i<=3;++i) { draw((i+8,0)--(i+8,3)); } for (int i=0;i<=3;++i) { draw((8,i)--(11,i)); } for (int i=0;i<=3;++i) { draw((i+12,0)--(i+12,3)); } for (int i=0;i<=3;++i) { draw((12,i)--(15,i)); } [/asy][/asy] Now, for $3\mid n>3$, we can, in each $3\times 3$ sub square, do each of the steps (i.e. first do Step 1 in all squares, then Step 2, then Step 3, then Step 4). Now, we show the hard part. Consider the generating function of the grid, where each cell in the $a$th row and $b$th column is given weight $x^{a-1}y^{b-1}$. Adding a tromino (lower left corner as $(a,b)$ increases our count by \[(1+x+y)x^ay^b\]while removing any row or column removes \[x^a\frac{y^n-1}{y-1},~y^b\frac{x^n-1}{x-1}\]respectively. This implies there exists $P(x,y)\in\mathbb Z[x,y],Q(x),R(x)\in\mathbb Z[x]$ such that \[(1+x+y)P(x,y)=\frac{y^n-1}{y-1}\cdot Q(x)+\frac{x^n-1}{x-1}\cdot R(y)\]In addition, note that the maximal power of $x$ in $P(x,y)$ is $n-2$, because the lower left corner can not be in the last row. Similarly, the maximal degree of $y$ is $n-2$ as well. Now, let $\omega=e^{2\pi i/n}$ and note that for all $1\leq a,b\leq n-1$, \[(1+\omega^a+\omega^b)P(\omega^a,\omega^b)=0\]Note that $1+\omega^a+\omega^b\neq 0$, so $P(\omega^a,\omega^b)=0$. Consider $P(\omega^a,y)$. It must be 0 in $n-1$ places, but has degree $n-2$, so thus is the zero polynomial. Thus, we can get \[x-\omega^a\mid P(x,y)\]for all $x,y$, but then this implies that the degree of $x$ is at least $n-2$, a blatant contradiction. Remarks. After trying for $n=2,3,4,5,6$, I came to the conclusion and construction for $3\mid n$. I was trying to see why exactly it would be necessary, and then remembered this idea of tiling with complex numbers to prove that something would have to be weight zero. The obvious tiling just straight up works, which is given by the multivariate polynomial. If you haven't seen the idea before, I think it's pretty hard to find, but once you find it, it becomes natural any time a similar problem appears.

I agree that it's the 3rd hardest, with U1 and U6 being harder. In contest however, I found it easier than U1, U2 and U6, because the more spatial thinking a problem involves, the harder it is for me.

Suppose $M(n)$ defines a square matrix of $n,$ initially empty. There are 3 rules that defines the progress in each subsequent iteration. If there is an $\ell$-shaped tromino region of three cells without stones on the board, you may place a stone in each of those cells. If all the 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. For $M(2)$ - $$\begin{bmatrix}\circ&&\circ\\\circ&&\circ\end{bmatrix}$$ Suppose that the tromino region begins with $a_{21}$ as the 'center-piece' - and that all subsequent trominos are made with the remaining empty pieces of the empty region of a now partially occupied $M(n)$ matrix. We can only make a new tromino if there is enough space for a tromino. $$\begin{bmatrix}\bullet&&\circ\\\bullet&&\bullet\end{bmatrix}$$ Now, apply either the 2nd or the 3rd rule. Applying the 2nd rule: $\begin{bmatrix}\bullet&&\circ\\\bullet&&\bullet\end{bmatrix}\rightarrow\begin{bmatrix}\circ&&\circ\\\circ&&\bullet\end{bmatrix}$ Applying the 3rd rule: $\begin{bmatrix}\bullet&&\circ\\\bullet&&\bullet\end{bmatrix}\rightarrow\begin{bmatrix}\bullet&&\circ\\\circ&&\circ\end{bmatrix}$ It can be seen that the final matrix for either rule is the transpost of the other. As the remaining space is a rotated L-shaped tromino, $M(2)$ cannot be solved. For $M(3)$ - $$\begin{bmatrix}\circ&&\circ&&\circ\\\circ&&\circ&&\circ\\\circ&&\circ&&\circ\end{bmatrix}$$. Start with a similar case to our $M(2)$ case. Because a row/column now needs 3 filled dots to apply, it's necessary that we use two L-shaped tromino's to apply either rule 2 or 3. $\begin{bmatrix}\circ&&\circ&&\circ\\\circ&&\circ&&\circ\\\circ&&\circ&&\circ\end{bmatrix}\rightarrow\begin{bmatrix}\circ&&\circ&&\circ\\\bullet&&\circ&&\circ\\\bullet&&\bullet&&\circ\end{bmatrix}\rightarrow\begin{bmatrix}\circ&&\bullet&&\circ\\\bullet&&\bullet&&\bullet\\\bullet&&\bullet&&\circ\end{bmatrix}$ Where we can clear either the $a_{21\rightarrow23}$ row or $a_{12\rightarrow32}$ column. Clearing the $a_{21\rightarrow23}$ row: $\begin{bmatrix}\circ&&\bullet&&\circ\\\bullet&&\bullet&&\bullet\\\bullet&&\bullet&&\circ\end{bmatrix}\rightarrow\begin{bmatrix}\circ&&\bullet&&\circ\\\circ&&\circ&&\circ\\\bullet&&\bullet&&\circ\end{bmatrix}$ Clearing the $a_{12\rightarrow32}$ column:$\begin{bmatrix}\circ&&\bullet&&\circ\\\bullet&&\bullet&&\bullet\\\bullet&&\bullet&&\circ\end{bmatrix}\rightarrow\begin{bmatrix}\circ&&\circ&&\circ\\\bullet&&\circ&&\bullet\\\bullet&&\circ&&\circ\end{bmatrix}$ Then we can add an L-tromino in the most convenient empty cells of either matrix. $\begin{bmatrix}\circ&&\bullet&&\circ\\\circ&&\circ&&\circ\\\bullet&&\bullet&&\circ\end{bmatrix}\rightarrow\begin{bmatrix}\bullet&&\bullet&&\circ\\\bullet&&\bullet&&\circ\\\bullet&&\bullet&&\circ\end{bmatrix}$ $\begin{bmatrix}\circ&&\circ&&\circ\\\bullet&&\circ&&\bullet\\\bullet&&\circ&&\circ\end{bmatrix}\rightarrow\begin{bmatrix}\circ&&\circ&&\circ\\\bullet&&\bullet&&\bullet\\\bullet&&\bullet&&\bullet\end{bmatrix}$ Applying either rule 2 or rule 3 twice on each respective matrix empties all cells.

The answer is \(3\mid n\), attained by dividing the \(n\times n\) board into \(3\times3\) squares and repeating the \(n=3\) construction in all \(3\times3\) squares simultaneously. Now we show that it is impossible to clear the board if \(3\nmid n\). Weight the squares of the board so that the cell \((i,j)\) has weight \(x^iy^j\), as shown below: \[ \begin{bmatrix} y^{n-1}&xy^{n-1}&x^2y^{n-1}&\cdots&x^{n-1}y^{n-1}\\ \vdots&\vdots&\vdots&\iddots&\vdots\\ y^2&xy^2&x^2y^2&\cdots&x^{n-1}y^2\\ y&xy&x^2y&\cdots&x^{n-1}y\\ 1&x&x^2&\cdots&x^{n-1} \end{bmatrix} \] Then adding a \(L\)-tromino is equivalent to increasing our net weight by a multiple of \(1+x+y\), removing a row is equivalent to decreasing our net weight by a multiple of \(1+x+\cdots+x^{n-1}\), and removing a column is equivalent to decreasing our net weight by a multiple of \(1+y+\cdots+y^{n-1}\). Thus if we eventually clear the board, there are polynomials \(P\), \(Q\), \(R\), with \(\deg_xP\le n-2\) and \(\deg_yP\le n-2\), such that \[P(x,y)\cdot(1+x+y)=Q(x,y)\cdot(1+x+\cdots+x^{n-1})+R(x,y)\cdot(1+y+\cdots+y^{n-1}).\]In particular if \(\omega_i,\omega_j\ne1\) are \(n\)th roots of unity then \[P(\omega_i,\omega_j)\cdot(1+\omega_i+\omega_j)=0.\] For \(3\nmid n\), we never have \(1+\omega_i+\omega_j=0\), so \(P(\omega_i,\omega_j)=0\) for all \(\omega_i\), \(\omega_j\). It follows that the polynomial (in \(x\)) \(P(x,\omega_j)\) has \(n-1\) roots for all \(\omega_j\), but its degree is at most \(n-2\), so \(P(x,\omega_j)\equiv0\). Then if \(P(x,y)=A_0(y)+A_1(y)\cdot x+A_2(y)\cdot x^2+\cdots\), we know \(A_k(\omega_j)=0\) for all \(\omega_j\), so \(A_k(y)\equiv0\), implying \(P(x,y)\equiv0\).

The answer is $3 \mid n$ only. For a construction, subdivide the board into $3 \times 3$ squares, and perform the construction for $n=3$ in each square. Now we will show that $3 \mid n$ is necessary. Take a root of unity $\omega = e^{\tfrac{2 \pi i}{n}}$, and set the values $(x,y) = (\omega^m,\omega^n)$ for any positive integers $m,n \leq n-1$. Set the weight of the square a distance $a$ from the left edge of the grid and a distance $b$ from the bottom edge of the grid by $x^ay^b$. For example, the bottom-left square would have weight $1$, while the top-right square would have weight $x^{a-1}y^{b-1}$. Define the support of a tromino to be the coordinate pair of the bottom-left cell of the tromino. Now, placing a tromino with support $(a,b)$ increases the weight by $(1+x+y)x^ay^b$. Removing any row or column does not decrease the weight of the board at all. Define the polynomial $P(x,y)$, which keeps track of the sum of all of the weights of the supports added. Note that $\deg P \leq n-2$ for both the coefficients of $x$ and $y$, since a support cannot be placed on the top or right edge of the grid. Now in the end state, we derive the equation $$(x+y+1)P(x,y) =0,$$when $x$ and $y$ are the $n$th roots of unity excluding $1$. Our aim is to show that $P$ is the zero polynomial. Remark that because $3 \nmid n,$ we cannot have $\omega^m+\omega^n+1 = 0$. This implies that $P (\omega^m,\omega^n) = 0$ for all $1 \leq m,n \leq n-1$. Now if we set $P(x,\omega^n)$ we can see that this single-variable polynomial has $\deg \leq n-2$ but $n-1$ zeroes; thus it must be the zero polynomial. Now we can determine $P$ is the zero polynomial by just expanding $P(x,y)$ (I think?)

Can I have a hint on this? I have already shown that $3|n$ works.

oops i'm bad

@above Do selection tests Day 1 P3 of https://artofproblemsolving.com/community/c4999_2004_india_imo_training_camp first (the pebbles one) (btw your answer is right) but in general, people don't really give hints on AoPS, so you should ask somewhere else, like in discord.

solved with #33's hint and ngl got another hint for finishing the end, solved anyways. Weight all the cells $(x,y)$ as $a^{x-1}b^{y-1}$, Then: $(1)$ Adding $L$-shaped tromino is equivalent to adding weight $ a^{x-1}b^{y-1}(1+a+b)$ where $a^{x-1}b^{y-1}$ is corner of the tromino and $x,y \in [1,n-2]$ $(2)$ Removing $k$-th row and column is equivalent to removing weight $ b^{k-1}(1+a+a^2+...+a^{n-1})$ and $ a^{k-1}(1+b+b^2+...+b^{n-1})$ respectively where $k \in [1,n-1]$ Assume that the prosses is possible for some $n$. Note that we will simplify the expressions using geometric sum formula. $$ (1+a+b) R(a,b)=\frac{a^n-1}{a-1} P(b)+ \frac{b^n-1}{b-1} Q(a)$$Let $a=\omega ^a, b= \omega ^b$ where $ \omega= e^{2\pi i/n}$. since definition of roots of unity is $z^n=1, z \neq 1$,Our equation becomes $$(1+\omega ^a+ \omega ^b) R(\omega^a,\omega^b)=0$$Note that $1+\omega^a+\omega^b=0$ is only possible if $\Re(\omega^a)= \Re( \omega^b)= - \frac{1}{2}$ and they are conjugate to each other, which is only possible if $3|n$ since $\omega^k = i\sin ( \frac{k(2 \pi)}{n} )+ \cos ( \frac{k(2 \pi)}{n})$, if $n$ is divisible by $3$, we can complete expressions to $-\frac{1}{2} + stuff$, otherwise is impossible. Now, assume $3|n$. Then we have $$ R(\omega^a,\omega^b)=0$$ Now, fix $a=\omega^a$. Then we have $ \deg ( R(\omega^a,b)) \le n-2$, but RHS has $n-1$ zero roots,which means $ R( \omega^a,b)=0$ Now, take any $a= \omega^a$ and expand $$R(\omega^a,b)= \sum_{k\ge 0} R_k( \omega^a)b^k=0$$. We have $ \deg ( R_k(\omega^a)) \le n-2$ and its degree changes when $k$ increases. But they are $0$ for $n-1$ values of $a$, Which gives $R_k(a)=0$, or $R(a,b)=0$. Which means that we can't even start the problem, hence $n \nmid 3$ is impossible. The only left is showing a construction $n|3$, which can be done by dividing $n \cdot n$ to $3 \cdot 3$ squares, using $2$ L shape to all the squares, delete the columns and add another $L$ and finish.

Only $3 \mid n$ works. For a construction, divide the board into $3 \times 3$ squares. In each, put a tromino in the bottom left of each square (trominoes are identified by their lower left corner), as well as the center. Then remove the center column. and place a tromino in the bottom middle of each square. Finish by removing two bottom rows. For $3 \nmid n$, index the rows and columns from $0$ to $n-1$, with the bottom left corner being $(0,0)$. Let $z=e^{2\pi i/n}$ be a primitive $n$-th root of unity. Suppose we weight cell $(i,j)$ with $w^{ai+bj}$ for some integers $1 \leq a,b \leq n-1$. Then the sum of weights along row $j$ is equal to $w^{bj}(1+w^a+\cdots+w^{a(n-1)})=0$, and likewise the sum of weights along each column is $0$. Suppose some sequence of moves works. Let $P(x,y)$ be a nonzero polynomial defined such that the coefficient of $x^iy^j$ equals the number of times we put a tromino on $(i,j)$; thus $P$ has degree at most $n-2$ in each variable. The sum of the weights of the cells with stones on them starts at $0$, should end at $0$, and changes by $x^iy^j(x+y+1)$ every time we add a tromino on $(i,j)$, so this total sum is $P(x,y)(x+y+1)$. This polynomial should vanish on $(x,y)=(z^a,z^b)$ for all integers $1 \leq a,b \leq n-1$ by our above observations. Since $3 \nmid n$, there is no choice of $a,b$ such that $z^a+z^b+1=0$, since the only two roots of unity summing to $-1$ are $e^{\pm 2\pi i/3}$. Thus $P(x,y)$ should vanish on all $(x,y)=(z^a,z^b)$. Fix $y=z^b$ for some arbitrary $b$. Viewed as a polynomial in $x$, $P(x,y)$ has degree at most $n-2$ but vanishes on $n-1$ values, namely on $z^a$ for all $1 \leq a \leq n-1$. Thus it must be identically zero, i.e. zero for all $x$. Now fix any $x \in \mathbb{C}$. As a polynomial in $y$, $P(x,y)$ has degree at most $n-2$ and vanishes on $n-1$ values, namely $z^b$ for all $1 \leq b \leq n-1$. Thus $P(x,y)$ vanishes (as a polynomial in $y$) for all $y$. Since $x$ is arbitrary, it follows that $P$ is identically zero: contradiction. $\blacksquare$ Remark: something something multiplicative weights fourier transform Since I was alive and clicking on threads in 2021 I have some memory of the solution, but this is instructive so I will type it out anyways to solidify memory or something

Solved with megarnie. The answer is $3\mid n$ only. First we provide a construction for $n= 3k$. Divide the grid into $k^2$ $3\times 3$ subgrids. In each of these subgrids, place a tromino centered at the bottom left cell of the subgrid and a tromino centered at the middle cell of the subgrid. Then delete the columns of the grid that align with the middle columns of the subgrids. Now, in each subgrid add a tromino centered at the bottom-middle cell. Then kill all rows. Now, we show that $3\mid n$ is necessary. First, label the rows $0,\dots n-1$ and the columns $0,\dots, n-1$ and assign coordinates $(i,j)$ to the cell at row $i$ and column $j$. Now, at any point in time define the polynomial \[ F(X,Y) = \sum_{(x,y)\in S}X^xY^y\]where $S$ is the multiset containing the coordinates of each stone on the grid. Suppose we arrive at an empty grid again. Let $T$ be the multiset of coordinates of the bottom left corners of the trominos placed. Then, the effect of the trominos on $F$ is an addition of \[\Delta_T = \sum_{(x,y)\in T}(X^xY^y + X^{x+1}Y^y + X^xY^{y+1}) = (1 + X + Y)\sum_{(x,y)\in T}X^xY^y.\]Now let $R$ be the multiset of $y$ coordinates of rows removed and $C$ the multiset of $x$ coordinates of columns removed. The effect of row and column removal on $F$ is a subtraction of \[\Delta_{RC} = \sum_{y\in R}Y^y(1 + \dots + X^{n-1}) + \sum_{x\in C}X^x(1 + \dots + Y^{n-1}).\]Since $F$ was $0$ both initially and finally, we must have \[ \Delta_T - \Delta_{RC} = 0\implies \Delta_T = \Delta_{RC}\]\[\implies (1 + X + Y)\sum_{(x,y)\in T}X^xY^y = \sum_{y\in R}Y^y(1 + \dots + X^{n-1}) + \sum_{x\in C}X^x(1 + \dots + Y^{n-1}).\]For brevity, let $G(X,Y) = \sum_{(x,y)\in T}X^xY^y$. Note that the RHS of the above equation vanishes when $X$ and $Y$ are both $n$th roots of unity. Hence the LHS does as well. In particular, \[ (1 + \alpha + \beta)G(\alpha, \beta) = 0,\qquad \forall \alpha,\beta\in \{\omega, \dots, \omega^{n-1}\}\]where $\omega$ is a primitive $n$th root of unity. Now, suppose $3\nmid n$. Then $1 + \alpha + \beta$ cannot equal $0$, as otherwise $\alpha,\beta,1$ would form an equilateral triangle, which is absurd. Thus $G(\alpha,\beta) = 0$ for each $(\alpha,\beta)$. There are $(n-1)^2$ pairs $(\alpha,\beta)$, so we have $(n-1)^2$ pairs on which $G(X,Y)$ vanishes. But $(1+X+Y)G$ has degree at most $n-1$ in each of $X$ and $Y$, i.e. $G$ has degree at most $n-2$ in each of $X,Y$. It follows that $G$ is identically $0$. This means we made no tromino moves, which means we made no row or column moves either. Thus no moves were made at all, contradiction.

We claim the answer is $3 \mid n$. Construction is relatively simple so just defer to one of the other posts, it's just $3 \times 3$ construction copied everywhere. Now, we will prove that $3 \mid n$ if $n$ works. We will begin by loosening the conditions of the operation to give us strictly more freedom. Assume that any cell can have any integer number of stones. Moreover, assume that we may decrease the number of stones by $1$ in each cell in a row or column, and increase the number of stones in each cell of an L. Finally, we will assume at least one L move will be performed. Notice that the original game is just a special case of our new game. Impose a coordinate system on the grid. Now, assume such moves described above are performed on the board. Consider the polynomial \[ P(x,y) = \sum_{(i,j) \in \{0,1, \ldots, n-1\}^2}c_{(i,j)}x^i y^j \]where $c_{(i,j)}$ is the number of stones in cell $(i,j)$ after the operations are performed. Thus, it is sufficient to prove that if $3 \nmid n$ then $P \not = 0$. Consider the L-operation. Notice that it is equivalent to choosing some $(i,j)$ and adding \[ x^iy^j + x^{i+1}y^j + x^iy^{j+1} = (x+y+1)x^iy^j\]To $P$. Moreover, notice that the row operation is equivalent to choosing some $i$ and subtracting \[ y^0x^i + y^1x^i + \cdots + y^{n-1}x^i = x^i(1+y+ \cdots +y^{n-1})\]From $P$. Symmetrically, column operations are equivalent to subtracting $y^i (1+x+ \cdots +x^{n-1})$. Thus, we want \[ (1+x+y)Q(x,y) – (1+ \cdots +y^{n-1})A(x) – (1+ \cdots +x^{n-1})B(y) = 0\]For some polynomials $Q,A,B$ with non-negative integer coefficients. Moreover, $Q \not = 0$ since at least one L move is performed. Thus, we want $x+y+1$ to divide the polynomial \[ (1+y+ \cdots +y^{n-1})A(x) + (1+x+ \cdots +x^{n-1})B(y) \]So, the expression above should vanish if $x+y+1 = 0 \implies y = -x-1$. Thus, we have. \[ \implies ((1+(-1-x)+ \cdots +(-1-x)^{n-1})A(x) + (1+x+ \cdots +x^{n-1})B(-1-x)=0 \]First, notice that we cannot operate on the topmost row, nor the leftmost column since the top left square is inaccessible to all the L moves. Thus $\deg A, \deg B \leq n-2$. We rewrite the expression as \[ \frac{1+x+ \cdots x^{n-1}}{1+(-1-x)+ \cdots +(-1-x)^n} = -\frac{B(-1-x)}{A(x)} \]Notice that the LHS has numerator and denominator of degree $n-1$ and the RHS has numerator and denominator of degree less than $n-1$. Thus, the two polynomials in the fraction of the LHS have a common root. Notice that this root must be some $n$’th root of unity $\omega$ since it is a root of the numerator. But, this would also imply that $-1-\omega$ is also a root of unity. But, for algebra reasons, $\omega$ and $-1-\omega$ can only both be roots of unity if $\omega$ is a third root of unity. Implying $3 \mid n$ as desired.

Absolutely lovely problem (only cuz gf works, lmfao). First we begin by proving this smol lemma.- Lemma: The only complex numbers $a,b$ in the unit circle with $a+b+1=0$ are $a=e^{\frac{2\pi i}{3}}$ and $b=e^{\frac{4 \pi i}{3}}$ Proof: It basically consists of a geometrical approach, considering this as a sum of vectors, in this case, it's basically saying that points $0+i0, a, -1+i0$ make an equilateral triangle because $b$ has modulus $1$ so this is just a result of graphing the sum process, since the same thing is true with $b$ we can wlog let $a$ be in $ri$ for $r>0$ and due to the equilateral we can just do basic trigonometry to get the desired answer. Now back to the problem we claim that all $3 \mid n$ work. Proof of Necessity: We will use generating functions in the following way, label the squares with coordinates from $(0,0)$ to $(n-1,n-1)$ going Left to Right and Down to Up, and now re-label $(a,b)$ with $x^ay^b$, so now assume that for some $n$ the process eventually vanished itself then FTSOC assume that $\gcd(3,n)=1$. Now from a $x^ay^b$ we denote its L-trimino (the L-trimino where it neighbours the other two cells) by $x^ay^b(1+x+y)$, now algebraically the process was just: $$\sum x^ay^b(1+x+y)=\left(\frac{y^n-1}{y-1} \right) P(x)+\left(\frac{x^n-1}{x-1} \right) Q(y)$$Where $P,Q$ are polynomials of degree at most $n-1$ because they denote the rows that have been deleted in the whole process, now by setting $y=-1-x$ note that if $\frac{(-1-x)^n-1}{-2-x}, \frac{x^n-1}{x-1}$ shared a common factor then let $\omega$ be a root of $x^n-1$ not equal to $1$ then we get that $-1-\omega$ is also a root of $x^n-1$ so by the lemma we end up getting that $\omega$ is a root of $x^3-1$ as well but that can't happen since $\gcd(3,n)=1$, therefore for each root $\omega$ of $x^n-1$ which is not $1$, we get that $P(\omega)=0$, by setting $x=-y-1$ and performing the exact same process we get that for any root $\omega$ of $x^n-1$ which is not $1$, $Q(\omega)=0$ must be true as well, by polynomial division this means that all the rows and all the columns have been deleted at some point which is a contradiction since we can never take the top-right cell, therefore $3 \mid n$ as desired. Proof of Sufficiency: Split the $n \times n$ grid in a bunch of $3 \times 3$, and in each use the bottom left and center L-triminos, then delete all possible columns and then fill with an L-trimino (from the square above bottom left in each), and clear all remaining rows to clear the entire board. Therefore both parts of the problem are complete, thus we are done .

Label each of the columns as $1$, $x$, $x^2$, $\dots$, $x^{n}$ where column $m$ has label $x^{m}$(columns labeled $0$ through $n-1$) and the rows analogously for $y$ instead of $x$. Then denote each of the cells in the board as the product of the label of the row and column. We will now consider the sum of all cells with a stone, $S$. Note that removing a column or row removes $y^k \cdot (1 + x + x^2 + \dots + x^{n-1})$ and $x^k \cdot (1 + y + y^2 + \dots + y^{n-1})$ where $k \in [1, n-1]$. Adding a tromino adds $x^{a}y_{b}(x+y+1)$ to $S$ where the bottom left square on the tromino lies on column $a$ and row $b$. Now, if there is some sequence of moves that ends in an empty board, it must hold true that \[(x+y+1)P_1(x, y) = \frac{x^n-1}{x-1} \cdot P_2(y) + \frac{y^n - 1}{y-1} \cdot P_3(x)\]This is true since $P_1$ is the sum of all $x^{a}y^b$ and $P_2$ and $P_3$ are all columns and rows we remove all stones from. We know that if a $n$ works, then $P_1(x,y)$ is not equal to $0$ for all $x$ and $y$ since we are adding a nonzero amount of trominoes. Plugging in $(x, y) = (\zeta^p, \zeta^q$ where $\zeta^i$ are $n$th roots of unity gives us that $(\zeta^p + \zeta^q + 1)(P_1(\zeta^p, \zeta^q) = 0$. We can apply Combinatorial Nullstellensatz(theorem $1$ here)where $S_1$ and $S_2$ are the set of $n$th roots of unity not equal to $1$. Applying this gives us that all coefficients of $P_1(x, y)$ are $0$ so we are done. It is only possible that $\zeta^p + \zeta^q + 1 = 0$ if $\zeta$ are $3$rd roots of unity, so if $n$ works then $3 \mid n$ must be true. For our construction, it suffices to just show it for a $3 \times 3$ board. Add trominoes with bottom left corners at $(0, 0)$ and $(1, 1)$. Then delete column $1$ and add trominoe with bottom left corner at $(1, 0)$ and delete rows $0$ and $1$. So we are done showing that all $n$ divisible by $3$.