
4. Let natural numbers $p, q(p<q)$ be given. Find the least natural number $m$ with the following property: the sum of all fractions whose denominators (in lowest terms) are equal to $m$ and whose values lie in the open interval $(p, q)$ is at least $56\left(q^{2}-p^{2}\right)$.


Solution. We show that the least $m$ is 113 (independent of $p, q$ ). Clearly $m>1$. For arbitrary natural numbers $c1$, let $S_{m}(c, d)$ denote the sum of all fractions (in their lowest terms) which lie in the open interval $(c, d)$ and whose denominator is $m$. Then we have the inequality

$$
S_{m}(c, c+1) \leqslant\left(c+\frac{1}{m}\right)+\left(c+\frac{2}{m}\right)+\cdots+\left(c+\frac{m-1}{m}\right)=(m-1) c+\frac{m-1}{2},
$$

with equality taking place if and only if all the numbers $1,2, \ldots, m-1$ are coprime with $m$, i.e. if and only if $m$ is a prime.

For any given natural numbers $p, q$ and $m>1$ we have

$$
\begin{aligned}
S_{m}(p, q)= & S_{m}(p, p+1)+S_{m}(p+1, p+2)+\cdots+S_{m}(q-1, q) \\
\leqslant & \left((m-1) p+\frac{m-1}{2}\right)+\left((m-1)(p+1)+\frac{m-1}{2}\right)+\ldots \\
& +\left((m-1)(q-1)+\frac{m-1}{2}\right)= \\
= & (m-1) \frac{(q-p)(p+q-1)}{2}+(m-1) \frac{q-p}{2}= \\
= & (m-1) \frac{q-p}{2}(p+q-1+1)=\frac{(m-1)\left(q^{2}-p^{2}\right)}{2},
\end{aligned}
$$

that is,

$$
S_{m}(p, q) \leqslant \frac{(m-1)\left(q^{2}-p^{2}\right)}{2}
$$

Moreover, equality takes place in (9) if and only if $m$ is a prime. However, by hypothesis

$$
S_{m}(p, q) \geqslant 56\left(q^{2}-p^{2}\right) .
$$

In view of $(9)$ we see that necessarily $\frac{1}{2}(m-1) \geqslant 56$, i.e. $m \geqslant 113$. As 113 is a prime, the least possible $m$ equals 113 .

## Final Round of the 56th Czech and Slovak Mathematical Olympiad  (March 18-21, 2007)

![](https://cdn.mathpix.com/cropped/2024_04_17_d54a2da2e34b65f1ad31g-21.jpg?height=165&width=381&top_left_y=325&top_left_x=556)
