Each cell of an $n \times n$ chessboard contains a lamp. At the beginning, two lamps located in two opposite corners are turned on, and the others are off. An operation consists of choosing a row (row or column) of the chessboard and changing the state of all the lamps in that row.

Before starting the operations, Alice can choose to turn on as many lamps as she wants individually. How many lamps must she turn on at a minimum so that there exists a sequence of operations after which all the lamps are off?
Let's already note that there is a solution by lighting $2 n-4$ lamps: if we number the rows and columns so that the lamps in cells $(1,1)$ and $(n, n)$ are initially lit, it suffices to light in addition all the lamps in cells $(m, 1)$ or $(n, m)$ with $m$ between 2 and $n-1$, then apply the operations to column 1 and row $n$. Let's now show that $2 n-4$ is the optimal solution.

We observe that if we choose any rectangle of cells on the board, the parity of the number of lit lamps among the four corners of this rectangle is an invariant. Therefore, in any rectangle having one of the cells $(1,1)$ or $(n, n)$ as a corner, we must light at least one other corner to hope that a sequence of the required operations exists.

We will therefore exhibit $2 n-4$ rectangles, one of whose corners is one of the initially lit cells, and whose corners are disjoint. Thus, we will have shown that at least $2 n-4$ cells must be lit. The $2 n-4$ rectangles announced are as follows:

- The $n-2$ rectangles whose corners are $(1,1),(1, m),(m, 1)$ and $(m, m)$, for $m$ between 2 and $n-1$.
- The $n-3$ rectangles whose corners are $(m, m-1),(m, n),(n, m-1)$ and $(n, n)$ for $m$ between 3 and $n-1$
- The rectangle with corners $(2, n-1),(2, n),(n, n-1)$ and $(n, n)$.

This concludes the proof.