Let \( n > 1 \) be a positive integer. List in increasing order all the irreducible fractions in the interval \([0, 1]\) that have a positive denominator less than or equal to \( n \): \[ \frac{0}{1} = \frac{p_0}{q_0} < \frac{p_1}{q_1} < \cdots < \frac{p_M}{q_M} = \frac{1}{1}. \] Determine, in function of \( n \), the smallest possible value of \( q_{i-1} + q_i + q_{i+1} \), for \( 0 < i < M \). For example, if \( n = 4 \), the enumeration is \[ \frac{0}{1} < \frac{1}{4} < \frac{1}{3} < \frac{1}{2} < \frac{2}{3} < \frac{3}{4} < \frac{1}{1}, \]where \( p_0 = 0, p_1 = 1, p_2 = 1, p_3 = 1, p_4 = 2, p_5 = 3, p_6 = 1, q_0 = 1, q_1 = 4, q_2 = 3, q_3 = 2, q_4 = 3, q_5 = 4, q_6 = 1 \), and the minimum is \( 1 + 4 + 3 = 3 + 2 + 3 = 3 + 4 + 1 = 8 \).
Problem
Source: Brazilian Mathematical Olympiad 2024, Level 3, Problem 6
Tags: number theory, Farey
12.10.2024 23:14
I'll add a solution here, but it is basically Farey property spam with casework bash mod 6
23.10.2024 23:33
First of all, we'll make use of the following two properties of Farey sequences: if $\frac ab$, $\frac pq$, $\frac cd$ are consecutive terms, then (1) $bp-aq = 1$ and (2) $\frac pq = \frac{a+c}{b+d}$. Also, the fractions $\frac ab$, $\frac pq$ are consecutive iff $bp-aq=1$ and $b+q > n$. In particular, two consecutive denominators are coprime. Let $f(n)$ be the answer. We'll show that $f(2) = 4$ and, for numbers greater than $2$, $f(6k-2) = 8k$, $f(6k-1) = f(6k) = 8k+2$, and $f(6k+1) = f(6k+2) = f(6k+3) = 8k+6$. First the examples: $\frac{k-1}{2k-1}, \frac{2k-1}{4k}, \frac{k}{2k+1}$ for $n=6k-2$; $\frac1{2k+1}, \frac2{4k+1},\frac1{2k}$ for $n=6k-1$ or $n=6k$; $\frac1{2k+2}, \frac2{4k+3}, \frac1{2k+1}$ for $n=6k+1$, $n=6k+2$, or $n=6k+3$. Now let's prove that we cannot do better. Let $\frac ab$, $\frac{a+c}{b+d}$, $\frac cd$ be three consecutive terms, and let $t = \gcd(a+c,b+d)$. Then the sum of the denominators is $s := b+\frac{b+d}t+d = (b+d)\frac{t+1}t$. However, $b + \frac{b+d}t \ge n+1$ and $d + \frac{b+d}t \ge n+1$, which implies $b+d+\frac{2(b+d)}t \ge 2n+2\iff b+d \ge (2n+2)\frac t{t+2}$. Therefore, $s \ge (2n+2)\frac t{t+2}\frac{t+1}t = (2n+2)\frac{t+1}{t+2} \ge \frac{4n+4}3$. A quick check with our examples shows that we found that $f(n) \le \frac{4n+14}3$. Quite close! However, if $t \ge 2$ then $s \ge \frac{3n+3}2 \ge \frac{4n+14}3$ for $n\ge 19$. Then, apart from the (not so) small cases $n\le 18$, one only needs to check the case $t=1$, for which the denominators are $b$, $b+d$, $d$, with sum $2(b+d)$ (an even number). With that in mind, the bound $s \ge \frac{4n+4}3$ for each $n\bmod 6$ are $f(6k-2) \ge 8k$ (OK), $f(6k-1) \ge 8k$ (not OK), $f(6k) \ge 8k+2$ (OK), $f(6k+1) \ge 8k+4$ (not OK), $f(6k+2) \ge 8k+4$ (not OK), and $f(6k+3) \ge 8k+6$ (OK). For $f(6k-1)$, the middle denominador is $4k$, and since the sum of two consecutive denominators is at least $6k$, each denominator is at least $2k$; but this implies that the denominators are $2k, 4k, 2k$, and consecutive denominators are not coprime, contradiction. Therefore $f(6k-1) \ge 8k+2$. For $f(6k+1)$ and $f(6k+2)$, the middle denominator is $4k+2$, and the other two are at least $2k$ and are coprime with $4k+2$; however, the smallest number in these conditions is at least $2k+3$, so the sum is at least $4k+2+2(2k+3) > 8k+4$, another contradiction. Therefore $f(6k+1), f(6k+2) \ge 8k+6$, and we are (mostly) done. The small cases $n\le 18$, $t\ge 2$ persist. Check cases $n \le 8$ manually; for the other cases, check each congruence mod $6$ more carefully: $f(9) \ge \frac{3\cdot 9+3}2 \implies f(9) \ge 15 > 14$; $f(10) \ge \frac{3\cdot 10+3}2 \implies f(10) \ge 17 > 16$, $f(11) \ge \frac{3\cdot 11+3}2 = 18$, $f(12) \ge \frac{3\cdot 12+3}2\implies f(12) \ge 20 > 18$; $f(13) \ge \frac{3\cdot 13+3}2 \implies f(13) \ge 21$; $f(14) \ge \frac{3\cdot 14+3}2 = 23 > 22$, $f(15) \ge \frac{3\cdot 15+3}2 \implies f(15) \ge 24 > 22$; $f(16) \ge \frac{3\cdot 16+3}3 \implies f(16) \ge 26 > 24$; $f(17) \ge \frac{3\cdot 17+3}2 = 27 > 26$; and $f(18) \ge \frac{3\cdot 18+3}2 \implies f(18) \ge 29 > 26$. The only case that remains is $n=13$, for which we need to prove that $f(13) \ge 22$; in this case, if $t \ge 2$ then $f(13) \ge \frac{3\cdot 13+3}4 = 21$; then one must have $t=2$, the denominatores are $b,\frac{b+d}2,d$, with $\frac{b+d}2 = 7$; but then $b+\frac{b+d}2 \ge 14$ implies $b \ge 7$ and, similarly, $d\ge 7$, and one can only have $b=d=7$, which is again impossible.