Sean $x_i = a_i/b_i$ y supongamos que $x_1 < x_2 < \cdots < x_n$. Sea $d = x_2 - x_1$. Afirmamos lo siguiente: Lema: Si $v_p(d) = -M$ para $M>0$, entonces 1. $\frac{2017}{2018} < \frac{5}{p^M} + \frac{1}{p}$ 2. Si $v_p(x_k) > -M$ entonces $k\equiv r\pmod{p}$ para algún entero fijo $r$. Demostración: Hacemos esto mostrando que $p^M$ debe dividir al menos $n - n/p-1$ de los $b_i$. Lo hacemos mediante casos sobre $v_p(x_1)$: 1. $v_p(x_1) < v_p(d)$. En este caso, $v_p(x_k) = v_p(x_1 + (k-1)d)$. Como $v_p(x_1) < v_p((k-1)d)$, se sigue que $v_p(x_k) = v_p(x_1) < -M$ para todo $k$, así que $v_p(b_k) > M$ y por lo tanto $p^M$ divide a todos los $n$ de los $b_i$. 2. $v_p(x_1) \ge v_p(d)$. Esto es equivalente a $v_p(p^Mx_k) > 0$, o $v_p(p^Mx_1 + (k-1)p^Md) > 0$. Ahora, nota que $v_p(p^Md) = 0$ y $v_p(p^Mx_1)\ge 0$, así que podemos tratar esto como una expresión modular: $(p^Mx_1) + (k-1) (p^Md)\equiv 0\pmod{p}$. Entonces se sigue que $k \equiv 1 - (p^Md)^{-1} (p^Mx_1)\pmod{p}$ donde tomar el inverso modular está definido ya que $v_p(p^Md) = 0$. Ahora, el número de enteros entre $1$ y $n$ que son equivalentes a $k\pmod{p}$ es menor que $n/p + 1$, así que más de $n - n/p - 1$ valores de $k$ no satisfacen $k\equiv r\pmod{p}$, lo que implica que más de $n-n/p - 1$ valores de $k$ satisfacen $v_p(x_k) = -M$. Para estos valores de $k$, tenemos $v_p(b_k) \ge M$, así que tenemos que $p^M$ divide a más de $n-n/p - 1$ de los $b_i$. Por otro lado, los $b_i$ son distintos, y hay a lo más $5n/p^M$ múltiplos de $p^M$ entre ellos, así que debemos tener $n-n/p-1<5n/p^M$ lo que implica $\frac{n-1}{n} < \frac{1}{p} + \frac{5}{p^M}$. Como $n \ge 2018$, obtenemos el lema deseado. $\blacksquare$ Ahora, resolviendo la desigualdad fácilmente da $p^M\in \{2, 4, 8, 3, 5\}$, así que si $v_p(d) < 0$ entonces $p\in \{2, 3, 5\}$. Ahora, supongamos que $x_k$ y $d$ tienen el mismo denominador al simplificar; es decir, $v_p(x_k) = v_p(d)$ siempre que $v_p(d) < 0$. Entonces por CRT y el lema anterior, se sigue que hay al menos $8$ residuos $r$ tales que podemos tener $k\equiv r\pmod{30}$. Sea $D$ el denominador de $d$ cuando se escribe en términos mínimos. Entonces por la discusión anterior, se sigue que $D\mid b_i$ para al menos $\lfloor n/30\rfloor\cdot 8$ de los $b_i$. Así que queda por acotar $D$. Ahora, claramente $d\ge \frac{1}{D}$, así que $x_k > \frac{k-1}{D}$. Además, entre las fracciones $x_i$, nota que $b_i\ge n/2$ para al menos $n/2$ de los $b_i$. Para estos términos, nota que $x_i = a_i/b_i \le (5n)/(n/2) = 10$, así que se sigue que $x_{n/2} \le 10$. Entonces $\frac{n/2-1}{D} < 10$, así que $n < 2(10D + 1) = 20D + 2$. Por lo tanto $n\le 20D+1$, así que hay a lo más $5n/D \le 105$ múltiplos de $D$ entre $1$ y $5n$. Pero $D\mid b_i$ para al menos $\lfloor n/30\rfloor\cdot 8 < 8(n/30 - 1)$ de los $b_i$. Así que $8(n/30 - 1) \le 105$ lo cual es una contradicción obvia, como se deseaba. $\square$

Olimpiada Internacional de Matemáticas , Lista Corta 2018 Problema N7

Problemas Recomendados

Recomendaciones