For any positive integers $n$ and $k$, let $f(n, k)$ denote the number of unit squares that the diagonal of an $n \times k$ rectangle passes through. How many pairs of numbers $n, k$ are there such that $n \geq k$, and $f(n, k)=2018$?
The diagonal connecting the lower left and the upper right vertex intersects $n-1$ horizontal and $k-1$ vertical grid lines inside the rectangle. It precisely passes through the interior of a (grid) unit square, different from the one in the upper right corner, if it intersects the right vertical or the upper horizontal side of that square.

![](https://cdn.mathpix.com/cropped/2024_05_02_d8ddeadd9ef5be948496g-1.jpg?height=285&width=417&top_left_y=302&top_left_x=843)

The total number of these intersection points is $(n-1)+(k-1)=n+k-2$. However, two such intersection points can coincide, which happens exactly when the diagonal passes through a grid point inside the rectangle. Such a grid point defines a $n_{1} \times k_{1}$ grid rectangle with the lower left vertex of the rectangle, where $\frac{n}{n_{1}}=\frac{k}{k_{1}}$, that is,

$$
n k_{1}=n_{1} k, \quad \text { and } \quad 1 \leq n_{1}<n, 1 \leq k_{1}<k \text { integers. }
$$

Let the greatest common divisor of $n$ and $k$ be $d$, then

$$
n=d n^{*}, \quad k=d k^{*}, \quad \text { where } n^{*} \text { and } k^{*} \text { are coprime. }
$$

Substituting into the previous equation:

$$
d n^{*} k_{1}=n_{1} d k^{*}, \quad \text { that is } \quad n^{*} k_{1}=n_{1} k^{*}
$$

This implies that $n_{1} k^{*}$ is divisible by $n^{*}$, which, due to the coprimality, only happens if $n_{1}$ is divisible by $n^{*}$: $n_{1}=x n^{*}$, where $x$ is a positive integer, and $n^{*} x<n=d n^{*}$, so $1 \leq x<d$; hence $k_{1}=x k^{*}$.

The number of interior grid points on the diagonal of the rectangle is thus equal to the number of possible values of $x$, which is $d-1$. This many unit squares were counted twice in the $n+k-2$ formula, so - including the unit square in the upper right corner that was previously omitted - the diagonal passes through $(n+k-2)-(d-1)+1=n+k-d$ unit squares.

Our task is thus to find the number of positive integer solutions to $n+k-d=2018$, where $(n, k)=d$ and $n \geq k$. Since $d$ is a divisor of both $n$ and $k$, $d \mid 2018=2 \cdot 1009$. The 1009 is prime, so the possible values of $d$ are: $1,2,1009$ and 2018.

1. If $d=1$, we seek the number of solutions to $n+k=2019=3 \cdot 673$ with $(n, k)=1$ and $n \geq k \geq 1$. Without the coprimality condition, the number of solutions would be 1009. However, those where both $n$ and $k$ are divisible by 3, 673, or 2019 are not valid. The number of such solutions is respectively $\left[\frac{1009}{3}\right]=336,\left[\frac{1009}{673}\right]=1$, and $\left[\frac{1009}{2019}\right]=0$, so the number of solutions satisfying all conditions in this case is $1009-(336+1)+0=672$.
2. If $d=2$, we seek the number of solutions to $n+k=2020=2^{2} \cdot 5 \cdot 101$ with $(n, k)=2$ and $n \geq k \geq 1$. This is clearly the same as the number of solutions to $x+y=1010=2 \cdot 5 \cdot 101$ with $(x, y)=1$ and $x \geq y \geq 1$. Using a similar calculation as in the first case, this is

$$
\begin{aligned}
505-\left(\left[\frac{505}{2}\right]+\left[\frac{505}{5}\right]+\right. & {\left.\left[\frac{505}{101}\right]\right)+\left(\left[\frac{505}{10}\right]+\left[\frac{505}{202}\right]+\left[\frac{505}{505}\right]\right)-\left(\left[\frac{505}{1010}\right]\right)=} \\
& =505-358+53-0=200
\end{aligned}
$$

3. If $d=1009$, we seek the number of solutions to $n+k=3027=3 \cdot 1009$ with $(n, k)=1009$ and $n \geq k \geq 1$. This is the same as the number of solutions to $x+y=3$ with $(x, y)=1$ and $x \geq y \geq 1$, which is clearly 1.
4. If $d=2018$, we seek the number of solutions to $n+k=4036=4 \cdot 1009$ with $(n, k)=2018$ and $n \geq k \geq 1$, which is 1, since only $n=k=2018$ satisfies the conditions.

Summing up the four cases, the number of pairs satisfying the problem is $672+200+1+1=874$.

# Using the solution of Döbröntei Dávid Bence (Pápa, Türr István Gymn. and Coll., 12th grade)

Note. If the prime factorization of an integer $m \geq 2$ is $n=p_{1}^{a_{1}} \cdot p_{2}^{a_{2}} \cdot \ldots \cdot p_{k}^{a_{k}}$, then the number of integers among any $m$ consecutive integers that are coprime to $m$ is $\varphi(m)=p_{1}^{a_{1}-1}\left(p_{1}-1\right) \cdot p_{2}^{a_{2}-1}\left(p_{2}-1\right) \cdot \ldots \cdot p_{k}^{a_{k}-1}\left(p_{k}-1\right)$. (This can also be proven using the sieve formula, which was used multiple times in the solution.) In the above solution, in all four cases, we sought the number of integer solutions to an equation of the form $x+y=m$ where $(x, y)=1$ and $x \geq y \geq 1$. Here $1 \leq y \leq\left[\frac{m}{2}\right]$, and the condition $(x, y)=1$ is precisely satisfied if $(y, m)=1$. Taking this into account, several solvers also reached the goal using the formula $\varphi(m)$.