
I-2 Consider a chessboard $n \times n$ where $n>1$ is a positive integer. We select the centers of $2 n-2$ squares. How many selections are there such that no two selected centers lie on a line parallel to one of the diagonals of the chessboard?


Solution. By a $k$-diagonal we mean any chessboard diagonal formed by $k$ squares, where $1 \leqslant k \leqslant n$. Since the number of stones is $2 n-2$, while the number of chessboard
diagonals in one direction is $2 n-1$ and two of them, which are 1-diagonals, must not be occupied by stones simultaneously, we can conclude that each $k$-diagonal with $k>1$ contains exactly 1 stone and that exactly two of the 4 corner squares (1-diagonals) are occupied (and lie on the same border side). Let us call two different directions of diagonals as A and B.

Now let us consider the set $P$ of all the pairs $(s, f)$, for which the stone $s$ lies on the same diagonal as the unoccupied ("free") square $f$. There are exactly $n^{2}-2 n+2$ free squares on the chessboard, two of them are corner, hence for each of the $n^{2}-2 n$ free squares $f$ which lie on two $k$-diagonals with $k>1$, we have $(s, f) \in P$ for exactly two stones $s$. Thus the total number $p$ of the pairs in $P$ is given by the formula

$$
p=2\left(n^{2}-2 n\right)+2=2 n^{2}-4 n+2
$$

where +2 stands for the two free corner squares.

If a stone $s$ lies on the intersection of a $k_{1}$-diagonal and a $k_{2}$-diagonal with $k_{1}, k_{2}>1$, then the number of pairs $(s, f) \in P$ with this $s$ equals $k_{1}+k_{2}-2$. The same holds also for the two other stones with $\left\{k_{1}, k_{2}\right\}=\{1, n\}$. Obviously, for any stone we have $k_{1}+k_{2} \geqslant n+1$ with equality iff the stone lies on a border square. Thus for each stone $s$, the number of pairs $(s, f) \in P$ is at least $n-1$, and therefore

$$
p \geqslant(2 n-2)(n-1)=2 n^{2}-4 n+2
$$

Since we have the equality, all the stones must lie on the boarder squares of the chessboard.

If we put some stones (even no stone) on the first horizontal row in any way, then the border squares for the other stones are determined in exactly one way. To see this, consider separately the four corner squares and then, for each $k, 1<k<n$, the pair of $k$-diagonals one direction together with the pair of $(n+1-k)$-diagonals in the other direction. Hence there are exactly $2^{n}$ possibilities how to distribute the stones on the chessboard as required.

Comment. The proof of the fact that all the stones must lie on some of the border squares from the preceding solution can be presented in the following algebraic form without counting the pairs $(s, f)$.

Consider the chessboard $n \times n$ as the grid $\{0,1, \ldots, m\} \times\{0,1, \ldots, m\}$ with $m=n-1$, in which the occupied squares are represented by points $\left(a_{i}, b_{i}\right)$ with $i=1,2, \ldots, 2 m$. Since $a_{i}-b_{i}$ are $2 m$ distinct integers from $\{-m,-m+1, \ldots, m-1, m\}$ and the boundary values $\pm m$ are not reached simultaneously, the values of $\left|a_{i}-b_{i}\right|$ (in nondecreasing order) are the numbers

$$
0,1,1,2,2, \ldots, m-1, m-1, m
$$

whose sum equals $m^{2}$. Thus we have

$$
\sum_{i=1}^{i=2 m}\left|a_{i}-b_{i}\right|=m^{2}
$$

and, similarly,

$$
\sum_{i=1}^{i=2 m}\left|a_{i}+b_{i}-m\right|=m^{2}
$$

Summing (1) and (2) and taking into account the identity

$$
|a-b|+|a+b-m|=\max (|2 a-m|,|2 b-m|) \quad \text { for any } a, b, m \in \mathbb{R}
$$

we obtain the equality

$$
\sum_{i=1}^{i=2 m} \max \left(\left|2 a_{i}-m\right|,\left|2 b_{i}-m\right|\right)=2 m^{2}
$$

Since $\left|2 a_{i}-m\right| \leqslant m$ and $\left|2 b_{i}-m\right| \leqslant m$ for each $i$, the following inequality

$$
\sum_{i=1}^{i=2 m} \max \left(\left|2 a_{i}-m\right|,\left|2 b_{i}-m\right|\right) \leqslant 2 m \cdot m=2 m^{2}
$$

holds and hence the equality (3) implies that

$$
\max \left(\left|2 a_{i}-m\right|,\left|2 b_{i}-m\right|\right)=m \quad \text { for any } i=1,2, \ldots, 2 m
$$

This means that any $\left(a_{i}, b_{i}\right)$ is a boundary point of the grid and the proof is complete.
