6. Two magicians perform the following act. At the beginning, the first magician locks the second magician in a booth where he can neither see nor hear anything. To start the game, the first magician invites Daniele, a member of the audience, to place on each square of an $n \times n$ chessboard, at his discretion, a white or black pawn. Then he asks Daniele to point out a square $C$ of his choice. At this point, the first magician chooses a square $D$ (not necessarily different from $C$) and replaces the pawn on $D$ with one of the other color (white with black or black with white).

The booth in which the second magician was locked is then opened. By observing the chessboard, the second magician manages to guess which is the square $C$. For which $n$ can the two magicians devise a strategy such that their act always succeeds?
SOLUTION: We will solve a slightly more general problem: suppose the chessboard can have any number $N$ of squares, not necessarily a square. We will show that the magicians have a strategy if and only if $N$ is a power of two. In the particular case $N=n^{2}$, it follows that $n$ must be a power of two.

If there is a strategy, then $N$ is a power of two. Let's count the number $D_{c}$ of configurations of pawns that the second magician associates with a specific square $c$. From any possible initial configuration, the first magician can reach one of these by making exactly one change, so every possible configuration must be reachable from one of the configurations associated with $c$ by changing exactly one pawn. Since there are $N$ possible pawn changes, $D_{c} \geq 2^{N} / N$. On the other hand, the sum of the numbers $D_{c}$ as $c$ varies among the $N$ possible squares is less than or equal to $2^{N}$. It follows that $D_{c}=2^{N} / N$ for every square $c$, so $N$ divides $2^{N}$.

If $N$ is a power of two, then there is a strategy. For $N=1$, the second magician cannot go wrong. For $N=2$, we call the two squares $x$ and $y$: the magicians agree to have a white pawn in the square $x$ if Daniel chose $x$, and a black pawn if Daniel chose $y$. Now, it suffices to show that if the magicians have a strategy for $N=a$ and for $N=b$, then they have a strategy for $N=a b$. The strategy consists in imagining the squares arranged in an $a \times b$ grid - with $a$ rows and $b$ columns - and stipulating that a row or column is white if it contains an even number of white pawns, black otherwise. In this way, changing the color of a pawn changes the color of precisely the row and the column on which it is located. The first magician determines the row and column on which the square chosen by Daniel is located, and uses the strategies for $N=a$ and $N=b$ on the colors of the rows and columns, respectively, decides to change the color of precisely one row and one column, and replaces the pawn at their intersection. The second magician considers the colors of the rows and columns, and applying the strategies for the cases $N=a$ and $N=b$ determines on which row and which column the square chosen by Daniel must be.