$n\times n$ chessboard game with coins

Question

The rows and the columns of an $n\times n$ chessboard are numbered $1$ to $n$, and a coin is placed on each field. The following game is played: A coin showing tails is selected. If it is in row $x$ and column $y$, then every coin with row number at least $x$ and a column number at least $y$ is turned over. This procedure is repeated. What is the number $L(n)$ for which it is possible to achieve in at most $L(n)$ steps that all coins on the board show heads, whatever be the initial distribution of heads and tails?

I proved by induction that it is always possible to achieve the final position in maximum $n^2$ steps, but I can't show for every $n$ a case where $n^2$ is actually needed.

Answer 1

If you start with every coin showing heads, and then select each coin once and perform the flipping move as described (with that coin as the "corner"), then the resulting board requires $n^2$ steps to return to the all-heads state. (And this generalized to non-square boards as well.)

The resulting board has tails in the square at row $i$, column $j$ if and only if both $i$ and $j$ are odd (although this isn't really necessary for proving the above statement).

To see why the statement is true, note that the coin at $(1,1)$ starts tails. It has to be itself selected if it's ever going to be flipped; and since the order of moves doesn't matter*, we might as well flip it first.

Then the two coins at $(1,2)$ and $(2,1)$ are tails, and the same logic applies: they have to be flipped sometime, no other coin can flip them**, and so we might as well flip them both right away.

Then continue in this way, addressing in turn all the coins at $(i,j)$ where $i+j=k$; we've already done $k=2$ and $k=3$.

*The order of moves does matter if we keep the restriction that we can only flip coins that are tails. However, if we drop this restriction and allow ourselves to choose any coin, then this argument shows that $n^2$ moves are still needed.

**Since selecting a single coin twice is the same as doing nothing to the board, we can assume that once a coin is selected, it will never be selected again.

Answer 2

Let $V:=\text{Mat}_{n\times n}\left(\mathbb{F}_2\right)$ be the set of $n$-by-$n$ matrices over $\mathbb{F}_2$, which is an $\mathbb{F}_2$-vector space. For each $i,j\in\{1,2,\ldots,n\}$, let $T_{i,j}$ denote the matrix whose $(a,b)$-entry is $1$ if $a\geq i$ and $b\geq j$, and is $0$ otherwise. Since $\dim_{\mathbb{F}_2}\left(V\right)=n^2$, no subset of size less than $n^2$ spans $V$. Hence, $L(n)\geq n^2$ is required. On the other hand, $\big\{T_{i,j}\,|\,i,j\in\{1,2,\ldots,n\}\big\}$ spans $V$ (or, rather, this set is of size $n^2$ and is linearly independent over $\mathbb{F}_2$, whence it is a spanning subset of $V$). Thus, $L(n)=n^2$.

---

If you are looking for an example where $n^2$ moves are needed, then look at $A:=\displaystyle\sum_{i=1}^n\,\sum_{j=1}^n\,T_{i,j}$. Then, if $A=\left[a_{\mu,\nu}\right]$, then $a_{\mu,\nu}=1$ if $\mu$ and $\nu$ are odd, and $a_{\mu,\nu}=0$ otherwise. The coin on the chessboard square $(\mu,\nu)$ has its tail turned up initially iff $a_{\mu,\nu}=1$.

---

---

More generally, on a $d$-dimensional chessboard of size $n_1\times n_2\times \ldots \times n_d$, we can play this game similarly. Let $t$ be a fixed positive integer. Instead of assigning a coin into each $d$-dimensional hypercube, we can assign each of the unit hypercubes an element of $\mathbb{Z}/(t\,\mathbb{Z})$, called the label of the hypercube. A move will consist of selecting a unit hypercube $\left(i_1,i_2,\ldots,i_d\right)$ and add $1$ to the label of every unit hypercube with index $\left(j_1,j_2,\ldots,j_d\right)$ such that $j_\mu\geq i_\mu$ for all $\mu=1,2,\ldots,d$. If $L_t\left(n_1,n_2,\ldots,n_d\right)$ is the smallest positive integer $\ell$ such that at most $\ell$ moves are required to change any initial state to the state in which all labels are $0$. Then, $$L_t\left(n_1,n_2,\ldots,n_d\right)=n_1n_2\cdots n_d\,(t-1)\,.$$The OP's problem is a special case where $t=2$, $d=2$, and $n_1=n_2=n$.

A proof consists of working with the unitary $\mathbb{Z}/(t\,\mathbb{Z})$-module $\displaystyle\bigotimes_{\mu=1}^d\,\big(\mathbb{Z}/(t\,\mathbb{Z})\big)^{\oplus n_\mu}$, which is free of rank $n_1n_2\cdots n_d$ (here $\otimes$ is the tensor product over $\mathbb{Z}/(t\,\mathbb{Z})$). Let $E_{i_1,i_2,\ldots,i_d}\in\displaystyle\bigotimes_{\mu=1}^d\,\big(\mathbb{Z}/(t\,\mathbb{Z})\big)^{\oplus n_\mu}$ be the element $e^{n_1}_{i_1}\otimes e^{n_2}_{i_2}\otimes\ldots\otimes e^{n_d}_{i_d}$, where $e^{n}_i$ denotes $(0,\ldots,0,1,0,\ldots,0)\in\big(\mathbb{Z}/(t\,\mathbb{Z})\big)^{\oplus n}$ with $1$ for the $i$-th entry. Write $T_{i_1,i_2,\ldots,i_d}$ for $\displaystyle\sum_{j_1=i_1}^{n_1}\,\sum_{j_2=i_2}^{n_2}\,\ldots\,\sum_{j_d=i_d}^{n_d}\,E_{j_1,j_2,\ldots,j_d}$. Then, $$\Big\{T_{i_1,i_2,\ldots,i_d}\,\Big|\,i_\mu\in\left\{1,2,\ldots,n_\mu\right\}\text{ for all }\mu=1,2,\ldots,d\Big\}$$ is a $\mathbb{Z}/(t\,\mathbb{Z})$-basis of $\displaystyle\bigotimes_{\mu=1}^d\,\big(\mathbb{Z}/(t\,\mathbb{Z})\big)^{\oplus n_\mu}$.

A more generalized version of this problem has been posted here: Game: Group and Multi-Dimensional Chessboard.