OBM 2024 Problem 6

Seja $n > 1$ um inteiro positivo. Enumere em ordem crescente todas as frações irredutíveis do intervalo $[0,1]$ que têm denominador positivo e menor ou igual a $n$:

$$\frac{0}{1} = \frac{p_0}{q_0} < \frac{p_1}{q_1} < \cdots < \frac{p_M}{q_M} = \frac{1}{1}.$$

Determine, em função de $n$, o menor valor possível de $q_{i-1} + q_i + q_{i+1}$, $0 < i < M$.

Por exemplo, se $n = 4$, a enumeração é

$$\frac{0}{1} < \frac{1}{4} < \frac{1}{3} < \frac{1}{2} < \frac{2}{3} < \frac{3}{4} < \frac{1}{1},$$

onde $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$ e o mínimo procurado é $1 + 4 + 3 = 3 + 2 + 3 = 3 + 4 + 1 = 8$.