We numbered the rows and columns of an $n \times n$ chessboard from 1 to $n$, then placed a coin on each of its squares. We play the following game: we select a coin on the board that is facing upwards. If the row and column numbers of this coin are $k$ and $m$, respectively, then we flip all coins whose row is at least $k$ and whose column is at least $m$. We repeat this step.

What is the smallest number $L(n)$ such that starting from any initial position, we can achieve that all coins show heads in at most $L(n)$ steps?
Solution. Define the variables $x_{i, j}$ and $y_{i, j}$ as follows:

\[
\begin{aligned}
x_{i, j} & = \begin{cases}0, & \text { if } i=0, \text { or } j=0, \\
0, & \text { if } i \neq 0, \text { and } j \neq 0, \text { and the }(i, j) \text { cell has heads, } \\
1, & \text { if } i \neq 0, \text { and } j \neq 0, \text { and the }(i, j) \text { cell has tails, }\end{cases} \\
y_{i, j} & = \begin{cases}0, & \text { if the sum } x_{i, j}+x_{i-1, j}+x_{i, j-1}+x_{i-1, j-1} \text { is even, } \\
1, & \text { otherwise. }\end{cases}
\end{aligned}
\]

If the coin on the $(i, j)$ cell is selected in one step, then $y_{i, j}$ changes. If $k \leq i$ and $\ell < j$, or $k > i$ and $\ell = j$, then two terms in the above sum change, so $y_{k, \ell}$ remains unchanged. If $k > i$ and $\ell > j$, then all four terms in the above sum change, so $y_{k, \ell}$ remains unchanged. Therefore, if the coin on the $(i, j)$ cell is flipped in one step, only $y_{i, j}$ changes, and the others do not.

Start from the table where the $(i, j)$ cell has tails if and only if $i \equiv j \equiv 1(\bmod 2)$ (i.e., both $i$ and $j$ are odd).

|  | 1 | 2 | 3 | 4 | 5 | 6 | $\ldots$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| 1 | T | H | T | H | T | H | $\ldots$ |
| 2 | H | H | H | H | H | H | $\ldots$ |
| 3 | T | H | T | H | T | H | $\ldots$ |
| 4 | H | H | H | H | H | H | $\ldots$ |
| 5 | T | H | T | H | T | H | $\ldots$ |
| 6 | H | H | H | H | H | H | $\ldots$ |
| $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\ddots$ |

It can be seen that for every $1 \leq i, j \leq n$, $y_{i, j}=1$. If all coins show heads, then for every $1 \leq i, j \leq n$, $y_{i, j}=0$. Therefore, it takes $n^{2}$ steps to transform the above table, so $L(n) \geq n^{2}$.

If there is any arbitrary table, then go through the coins row by row in the positive direction. If a coin shows tails, flip it. In one step, the previously traversed coins do not flip, so they all show heads. If all coins have been traversed, then all will show heads. Each coin is flipped at most once, so there are at most $n^{2}$ steps, hence $L(n) \leq n^{2}$.

Therefore, $L(n)=n^{2}$.