PS: I have been there, and learn that nice solution after the IMO

Solution. Clearly, cases with $ n = 1,2$ are solvable, and a $ 1\times 3$ "tile" can be deleted if there exists an empty and full square to the left and right of an end of the tile. Hence, a $ n\times n$ square can be reduced to a $ n\bmod 3\times n\bmod 3$. If $ 3\nmid n$, then we are done. Assume to the contrary that a $ 3n\times 3n$ square can be reduced to one point. Consider the function $ f: \mathbb{N}^2\rightarrow \mathbb{Z}_3$ such that $ f(a,b) = a + b\bmod 3$. Let $ f_0,f_1,f_2$ be the cardinality of the set of preimages of $ 0,1,2$, respectively. Since initially $ f_0 = f_1 = f_2 = 3n^2$ and each step reduces two and increases one of $ f_0,f_1,f_2$ by 1, $ f_0\equiv f_1\equiv f_2\pmod 2$ at all times. Ergo, $ (f_0,f_1,f_2)\neq (0,0,1), (0,1,0),(1,0,0)$. And the conclusion follows. $ \Box$

Isn't it just a special case of Russia 1992 Grade 9 problem 4, Given an infinite sheet of square ruled paper. Some of the squares contain a piece. A move consists of a piece jumping over a piece on a neighbouring square (which shares a side) onto an empty square and removing the piece jumped over. Initially, there are no pieces except in an m x n rectangle (m, n > 1) which has a piece on each square. What is the smallest number of pieces that can be left after a series of moves? I think it is very interesting.

anonymous1173 wrote: Isn't it just a special case of Russia 1992 Grade 9 problem 4, Given an infinite sheet of square ruled paper. Some of the squares contain a piece. A move consists of a piece jumping over a piece on a neighbouring square (which shares a side) onto an empty square and removing the piece jumped over. Initially, there are no pieces except in an m x n rectangle (m, n > 1) which has a piece on each square. What is the smallest number of pieces that can be left after a series of moves? I think it is very interesting. Yes, it is. Dieter Gronau writes in his report on IMO'1993: Erst während der Klausur wurde bekannt, daß die 3. Aufgabe, die von Finnland eingereicht worden war, im vergangenen Jahr bei der All-Republiks-Olympiade der GUS in Alma-Ata, an der wohl alle Nachfolgestaaten der UdSSR, außer dem Baltikum, teilnahmen, gestellt worden war. Keiner der Leiter dieser Delegationen informierte die Jury. Selbst der russische Delegationsleiter (Prof. Vavilov) informierte die Jury nicht, obwohl er erst kürzlich einen Artikel in Quant über diese Olympiade veröffentlichte. Einer der Stellvertreter, die die Aufgaben erst während der Klausur erhalten, deckte diesen Sachverhalt auf. Es gab eine lange und sehr kontroverse Diskussion in der Jury. Einerseits wird dieser Sachverhalt nicht vom Reglement überdeckt und jeder hatte Zugang zu diesem Artikel. Andererseits empfanden es viele Delegationsleiter als unakzeptabel im Hinblick auf die Bestrafung der Teilnehmer hier nichts zu unternehmen. Allerdings lassen die Ergebnisse der Teilmehmer aus diesen Ländern nicht darauf schließen, daß die Schüler die Aufgabe gut kannten. Die Anträge auf Abstimmung in der Jury reichten von der namentlichen Verurteilung des russischen Delegationsleiters bis zur Ignorierung des Sachverhaltes. Schießlich wurde folgende Erklärung von der Jury mehrheitlich angenommen (13 Ja, 10 Nein, 46 Enthaltung): Die Jury der 34. IMO mißbilligt die Inaktivität der Leiter einiger Delegationen hinsichtlich der 3. Aufgabe.

The case for a $3n \times 3n$ square can be solved nicely by using a simple colouring/invariance argument: colour the squares of the infinite chessboard with 3 colours $(a,b,c)$ such that you have a bottom-left-to-top-right diagonal of colour $a$ next to a bottom-left-to-top-right diagonal of colour $b$ next a bottom-left-to-top-right diagonal of colour $c$ and so on. Now let the total number of pieces on squares coloured with colour $a$ be $A$; define $B,C$ similarly. Now any move keeps the parities of $A-B, B-C, C-A$ the same: e.g. if you move from a square of colour $a$ to one of colour $c$ then $A$ goes to $A-1$, $B$ goes to $B-1$ and $C$ goes to $C+1$ and so $A-B$ stays the same while $B-C$ decrease by $2$ and $C-A$ increases by $2$. At the start the values of $A-B, B-C, C-A$ are all $0$ (there are the same number of pieces $(=3n^2)$ on each type of square). While in the configuration we are trying to get to, two of $A-B, B-C, C-A$ are odd. So the configuration can't be reached.

I'll prove that $3|n$ then the statement is false first color the chessboard as below let $S$ the sum of occupied square firstly $S=0$ note that in each move $S$ by $2\omega^i$ so at the end $S=2a+2b\omega +2c\omega^2=\omega^i=2a'+2b'\omega$ case(1):$b'=0 \implies 2a'=1$ a contradiction case(2): $b' \neq 0 \implies \omega \in Q$ a contradiction and we win

Solution from Twitch Solves ISL: The answer is all $n$ not divisible by $3$. First, we show the task is impossible when $3 \mid n$. Color the board periodically red, green, blue as shown: \[ \begin{bmatrix} R & G & B & R & G & \dots \\ G & B & R & G & B & \dots \\ B & R & G & B & R & \dots \\ R & G & B & R & G & \dots \\ G & B & R & G & B & \dots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{bmatrix} \]Note that every move changes the parity of the number of tokens of each color. When $3 \mid n$, there are an equal number of tokens of each color, so it is impossible to arrive at one token of one color and none of the others. We now devise an algorithm for $3 \nmid n$. This requires two parts: Claim: Suppose we have the following configuration, where a $\bullet$ represents a cell with a token and a $\square$ represents an empty cell (blank cells have no requirement imposed): \[ \begin{bmatrix} & \bullet & \\ & \bullet & \\ \square & \bullet & \bullet \\ \end{bmatrix} \]Then we can remove the three cells in the center column. Proof. Jump the lower-right corner, then the upper counter, then the lower-left counter. $\blacksquare$ Using this, we can show $n=4$ is possible in the following way: \begin{align*} \begin{bmatrix} \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \end{bmatrix} &\mapsto \begin{bmatrix} \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \end{bmatrix} \mapsto \begin{bmatrix} \bullet \\ \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \end{bmatrix} \\ &\mapsto \begin{bmatrix} \\ \\ & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \end{bmatrix} \mapsto \begin{bmatrix} \\ \\ & \bullet & \bullet & \bullet \\ & & & \bullet \\ \end{bmatrix} \mapsto \begin{bmatrix} \\ \\ \\ \bullet & \phantom{\bullet} & \phantom{\bullet} & \phantom{\bullet} \end{bmatrix} \\ \end{align*}This lets us to reduce an $(n+3) \times (n+3)$ square to an $n \times n$ square in the following way: [asy][asy] size(5cm); filldraw(scale(7)*unitsquare, invisible, red); label("$n \times n$", (3.5, 3.5), red); for (int i=0; i<3; ++i) { dot( (0.5, 7.5+i), green); dot( (1.5, 7.5+i), blue); dot( (2.5, 7.5+i), green); dot( (3.5, 7.5+i), blue); dot( (4.5, 7.5+i), green); dot( (5.5, 7.5+i), blue); dot( (7.5+i, 0.5), green); dot( (7.5+i, 1.5), blue); dot( (7.5+i, 2.5), green); dot( (7.5+i, 3.5), blue); dot( (7.5+i, 4.5), green); dot( (7.5+i, 5.5), blue); } draw(shift(6,6)*scale(4)*unitsquare, black); dot((6.5, 6.5), red); for (int i=0; i<=3; ++i) { for (int j=0; j<=3; ++j) { if (i+j>0) { dot((6.5+i, 6.5+j), black); } } } [/asy][/asy] Remove the green and blue dots shown in alternating waves, then repeat the strategy with $n=4$ to remove all black dots. Finally, the base cases $n = 1$ and $n = 2$ are easy to do by hand, finishing the problem.

$ $

Solved with stillwater_45. Very interesting problem! Badly written up solution, unfortunately without nice diagrams. We claim that the game can end with only one piece remaining on the board if and only if $3 \nmid n$. We first show the necessity of this condition. Claim : For all $3 \mid n$, it is impossible to end the game with only one piece remaining on the board. Proof : Color the board in three colors, such that every up-right/down-left diagonal consists of cells of the same color, and the colors of the diagonals alternate between red, blue and green in that order. Let $R,B$ and $G$ denote the number of pieces placed on a red, blue or green cell respectively. Now, consider the quantities $S_{BR}=B+R$ , $S_{RG}=R+G$ and $S_{GB}=G+B$. We first focus on $S_{BR}$. Note that, each move is one of three types. 1. A red piece jumps over a blue piece onto a green cell (or vice versa) 2. A blue piece jumps over a green piece onto a red cell (or vice versa) 3. A red piece jumps over a green piece onto a blue cell (or vice versa) In the first of the above moves, $S_{BR}$ decreases by 2, and in the other two it remains unchanged. Thus, the parity of $S_{BR}$ is an invariant under the described moves. Note that since $3\mid n$, we start off with $R=B$, so $2 \mid S_{BR}$. Further, in the final state, we are left with only one piece which may lie on either a green cell (so $S_{BR}=0$) or a red/blue cell (so $S_{BR}=1$). However, the requirement that the parity of $S_{BR}$ does not changes forces $S_{BR}=0$ and thus, the final piece lies on a green cell. Repeating this argument with $S_{RG}$ and $S_{GB}$ indicate that the final piece lies on a blue and red cell respectively. However, none of the cells are all red, green and blue so this is a very clear contradiction. We provide an inductive construction. Note that when $n=1$ and $n=2$ it is quite easy to reach a state with exactly one piece. Before we can settle other $n$, we need to create some important algorithms. Algorithm : Any three pieces in a row/column (adjacent cells) which have three pieces in the row/column below/to the left of them can be removed from the board without changing the positions of any other pieces. Proof : Consider 6 pieces labeled $1$ to $6$ placed in a $2 \times 3$ grid as follows. We show that the pieces $1,2$ and $3$ can be removes from the board without changing the positions of the other pieces. \begin{tabular}{|c|c|c|} \hline 1& 2 & 3 \\ \hline 4& 5 & 6 \\ \hline \end{tabular}Piece $4$ moves over piece $1$ removing it from the board. Piece $3$ then moves over piece $2$, and piece $4$ moves over piece $3$ returning to it's original position. Algorithm : If all cells of a $2 \times 3$ grid, which has no pieces adjacent to one of the columns/ rows of length 3 contain a piece, it can be rearranged to a row of three cells containing pieces, without doing any other changes. Proof : Consider 6 pieces labeled $1$ to $6$ placed in a $2 \times 3$ grid as follows, with the cells above pieces $1,2$ and $3$ empty. \begin{tabular}{|c|c|c|} \hline 1& 2 & 3 \\ \hline 4& 5 & 6 \\ \hline \end{tabular}Piece $6$ moves over piece $3$ and piece $5$ moves over piece $2$. Then, piece $6$ moves over piece $5$ and we are left with pieces $6$ , $1$ and $2$ in a row. Now we are in a position to perform the induction. The base case of $n=2$ being clear, we deal with $n=4$. With the first algorithm, remove the top-right corner row of three pieces and the two bottom-right corner rows of three pieces. This leaves us with the board looking like, \begin{tabular}{|c|c|c|c|} \hline 1& & & \\ \hline 2& 5 & & \\ \hline 3 & 6 & & \\ \hline 4 & 7 & & \\ \hline \end{tabular}Now, piece $6$ moves over piece $3$, piece $1$ moves over piece two and piece $3$ moves over piece $1$. Finally, piece $4$ moves over piece $7$ , piece $5$ moves over piece $6$ and finally piece $5$ moves over piece $5$, leaving exactly one piece (piece $4$) left on the board. Now, assume that the condition holds for $n=3k+1$ and $n=3k-1$ for some $k \ge 1$. For $n=3k+2$, perform the first algorithm on the first $3k$ rows of the right-most three columns, and then on the first $3$ rows of columns $2$ to $3k-3$. This leaves use with a $(3k-1 \times 3k-1)$ grid with two $2\times 3$ grids attached. Perform the second algorithm on these smaller grids, which reduces them to two rows of three, which can then be deleted using the first algorithm. Then, we are left with a $(3k-1 \times 3k-1)$ grid of pieces, which eventually ends with one piece left on the board by the inductive hypothesis. For $n=3k+4$, perform the first algorithm on the top-right corner two rows of three cells, the first $3$ rows of columns $3$ to $3k+2$ and the rows $4$ to $3k+2$ of the right-most three columns. This again leaves us with a $(3k+1 \times 3k+1)$ grid of pieces with two $2\times 3$ grids attached, which we eliminate exactly as before, completing the induction.