Olimpiadi di Matematica - Febbraio

Solution:

The answer is $\mathbf{( C )}$. We need to count the pairs $(m, n)$ such that $314/100 \leq m / n < 315 / 100$. Equivalently, we want to determine how many pairs $(m, n)$ there are such that $14 / 100 \leq (m-3 n) / n < 15/100$. Let us define $k = m - 3 n$ and count the pairs $(k, n)$ such that $14 / 100 \leq k / n < 15 / 100$. Since $n < 100$, $k < 15 n / 100 < 15$. Let us therefore consider separately the cases $k = 1, 2, \ldots, 14$. For each such $k$, rewriting the inequalities, we want to count how many integers $n < 100$ satisfy
$$\frac{100}{15} k < n \leq \frac{100}{14} k$$
that is
$$-\frac{k}{3} < (n - 7 k) \leq \frac{k}{7}$$
So it suffices to count, for each of these intervals $(-k / 3, k / 7]$, how many integers they contain. For $k = 1, 2, 3, \ldots, 14$ we have respectively $1, 1, 1, 2, 2, 2, 4, 4, 4, 5, 5, 5, 6, 7$. However, for $k = 14$, we are not allowed to count $n = 100$. Thus the answer is $3 \cdot 1 + 3 \cdot 2 + 3 \cdot 4 + 3 \cdot 5 + 6 + 7 - 1 = 48$.

Second solution. As above, we want to count the pairs $(m, n)$ such that $314/100 \leq m / n < 315 / 100$. We are thus counting the number of points with integer coordinates $(m, n)$ in the plane subject to the conditions:
$$314 n - 100 m \leq 0, \quad 315 n - 100 m > 0, \quad 0 < n < 100.$$
The points satisfying these conditions form a triangle with vertices $O = (0, 0)$, $A = (314, 100)$, $B = (315, 100)$, including the segment $OA$, but excluding the other two. The points with integer coordinates lying inside a segment having one vertex at the origin are the multiples of the pair of coordinates of the other vertex, once reduced to lowest terms. Thus for $OA$ there are $\operatorname{MCD}(314, 100) - 1 = 1$, for $AB$ there are $\operatorname{MCD}(315 - 314, 100 - 100) - 1 = 0$, for $OB$ there are $\operatorname{MCD}(315, 100) - 1 = 4$. By Pick's theorem applied to the triangle $OAB$,
$$a = i + \frac{b}{2} - 1$$
where $a = 100 \cdot (315 - 314) / 2$ is the area of $OAB$, $i$ is the number of points with integer coordinates inside $OAB$ and $b = 3 + 1 + 0 + 4$ is the number of points with integer coordinates on the boundary of $OAB$; hence $i = 47$. The answer is given by the points inside $OAB$ plus those inside the segment $OA$, that is $i + 1 = 48$.