1. Given a natural number n. A square with side length n is divided into $n^{2}$ unit squares. The distance between two squares is considered to be the distance between their centers. Determine the number of pairs of squares whose distance is 5.
SOLUTION. We will express the position of unit squares in the solution using coordinates - a square in the $r$-th row and $s$-th column will be denoted by $(r, s)$. Using the Pythagorean theorem, we can easily see (Fig. 1) that the square $(r, s)$ is at a distance of 5 from the squares

$$
\begin{aligned}
& (r, s+5), (r+5, s), (r+3, s+4), (r+4, s+3), (r+3, s-4), \quad (r+4, s-3), \\
& (r, s-5), \quad (r-5, s), (r-3, s-4), (r-4, s-3), (r-3, s+4), \quad (r-4, s+3).
\end{aligned}
$$

In total, we have at most 12 possibilities; fewer if some of the coordinates correspond to a position outside the $n \times n$ square, i.e., if they do not lie in the set $\{1,2, \ldots, n\}$.

![](https://cdn.mathpix.com/cropped/2024_04_17_9d0acb5b9a4664e7b944g-01.jpg?height=568&width=580&top_left_y=1201&top_left_x=744)

Fig. 1

First, let's calculate the number of pairs of squares of the type $\{(r, s), (r, s+5)\}$, i.e., "horizontal" pairs. If $n \geq 5$, there are $n-5$ such pairs in each of the $n$ rows, because for a fixed $r$, $s$ can take the values $1, 2, \ldots, n-5$. In total, there are $n(n-5)$ "horizontal" pairs. By symmetry, there are the same number of "vertical" pairs.

The number of pairs of squares of the type $\{(r, s), (r+3, s+4)\}$ is $(n-4)(n-3)$ (if $n \geq 4$), because $r$ can take the values $1, 2, \ldots, n-3$ and $s$ can take the values $1, 2, \ldots, n-4$. By symmetry, the number of pairs of squares of the types $\{(r, s), (r+4, s+3)\}$, $\{(r, s), (r+3, s-4)\}$, and $\{(r, s), (r+4, s-3)\}$ is the same.

Since we are interested in the number of unordered pairs of squares, we will not count the other possibilities from (1) (otherwise, we would count each pair twice). Therefore, the total number of pairs of squares in the case $n \geq 5$ is

$$
2 n(n-5) + 4(n-4)(n-3) = 2(3 n^2 - 19 n + 24).
$$

For $n \leq 4$, the desired number is clearly 0.

Note. The problem can also be solved as follows: In each square of the large square, we write a number indicating the number of squares that are at a distance of 5 from it. To find the result, it is enough to sum all the written numbers and divide the sum by two (each pair of squares is counted twice in the sum). If a square is at least 5 units away from the edge squares of the square (i.e., its coordinates $(r, s)$ satisfy the inequalities $6 \leq r, s \leq n-5$), the number 12 is written in it. It is enough to investigate the numbers near the edges of the square, and especially near its

![](https://cdn.mathpix.com/cropped/2024_04_17_9d0acb5b9a4664e7b944g-02.jpg?height=783&width=788&top_left_y=565&top_left_x=634)

corners. The disadvantage of this approach is that it is necessary to investigate the situations for $n \leq 9$ separately, when the edge areas are smaller than in the general case $n \geq 10$, which is illustrated in Fig. 2. For $n \geq 10$, the number of pairs is

$$
\frac{1}{2}\left(12(n-10)^2 + 4(n-10)(11 + 9 + 3 \cdot 7) + 4(10 + 2 \cdot 8 + 7 \cdot 6 + 6 \cdot 5 + 9 \cdot 4)\right)
$$

and similar expressions (without the variable $n$) can be written for the individual cases $n \in \{9, 8, 7, 6, 5\}$ based on Figs. 3a to 3e. It can be verified (and it follows from the previous solution) that all these expressions can be represented by the single formula $2(3 n^2 - 19 n + 24)$.

$$
\begin{array}{|l|l|l|l|l|}
\hline 2 & 1 & 0 & 1 & 2 \\
\hline 1 & 0 & 0 & 0 & 1 \\
\hline 0 & 0 & 0 & 0 & 0 \\
\hline 1 & 0 & 0 & 0 & 1 \\
\hline 2 & 1 & 0 & 1 & 2 \\
\hline
\end{array}
$$

Fig. 3a

| 4 | 3 | 2 | 2 | 3 | 4 |
| :--- | :--- | :--- | :--- | :--- | :--- |
| 3 | 2 | 1 | 1 | 2 | 3 |
| 2 | 1 | 0 | 0 | 1 | 2 |
| 2 | 1 | 0 | 0 | 1 | 2 |
| 3 | 2 | 1 | 1 | 2 | 3 |
| 4 | 3 | 2 | 2 | 3 | 4 |

Fig. 3b

N1. How many pairs of squares in an $n \times n$ square have a distance of 2? [If $n \geq 2$, there are $n-2$ such pairs in each row and the same number in each column. In total, there are $2 n(n-2)$.]

N2. How many pairs of squares in an $n \times n$ square have a distance of $\sqrt{5}$? [For $n \geq 2$, there are $4(n-1)(n-2)$.]

| 4 | 4 | 3 | 3 | 3 | 4 | 4 |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- |
| 4 | 4 | 3 | 3 | 3 | 4 | 4 |
| 3 | 3 | 2 | 2 | 2 | 3 | 3 |
| 3 | 3 | 2 | 0 | 2 | 3 | 3 |
| 3 | 3 | 2 | 2 | 2 | 3 | 3 |
| 4 | 4 | 3 | 3 | 3 | 4 | 4 |
| 4 | 4 | 3 | 3 | 3 | 4 | 4 |

Fig. 3c

| 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- |
| 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
| 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
| 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
| 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
| 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
| 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
| 4 | 4 | 4 | 4 | 4 |