
1. Paul is filling the cells of a rectangular table alternately with crosses and circles (he starts with a cross). When the table is filled in completely, he determines his score as $X-O$ where $X$ is the sum of squares of the numbers of crosses in all the rows and columns, and $O$ is the sum of squares of the numbers of circles in all the rows and columns. Find all possible values of the score for a $67 \times 67$ table.

(Josef Tkadlec)


Solution. Let $n=67$ and denote by $k=\frac{1}{2}\left(n^{2}+1\right)$ the total number of crosses in the table. A row containing $a$ crosses and $n-a$ circles contributes $a^{2}-(n-a)^{2}=2 n \cdot a-n^{2}$ to the total score and thus all the $n$ rows combined contribute

$$
2 n \cdot k-n \cdot n^{2}=2 n \cdot \frac{n^{2}+1}{2}-n^{3}=n
$$

to the total score. Likewise, columns contribute $n$. Hence the total score is always equal to $2 n=134$.

Another solution. Consider an $n \times n$ table filled with arbitrarily many crosses and circles. We show that replacing any circle by a cross increases the score by $4 n$. Since the score for a table filled with all circles equals $-2 n^{3}$ and Paul's table contains $\frac{1}{2}\left(n^{2}+1\right)$ crosses, the final score will always be equal to $-2 n^{3}+4 n \cdot \frac{1}{2}\left(n^{2}+1\right)=2 n$.

Consider any cell containing a circle and denote by $r$ and $c$ the number of crosses in its row and column, respectively. The contribution of this row and column changes from

$$
A=r^{2}-(n-r)^{2}+s^{2}-(n-s)^{2}=2 n(r+s)-2 n^{2}
$$

to

$$
B=(r+1)^{2}-(n-r-1)^{2}+(s+1)^{2}-(n-s-1)^{2}=2 n(r+1+s+1)-2 n^{2}
$$

and the contribution of other rows and columns doesn't change. Since $B-A=4 n$, we are done.
