Problema 1 del segundo nivel de la XXV Olimpiada de Mayo (2019) Se dirige a una edad de 14 años
Un entero es piola si los 9 restos que se obtienen al dividirlo entre 2, 3, 4, 5, 6, 7, 8, 9 y 10 son todos diferentes y distintos de cero.
¿Cuántos enteros piolas hay entre 1 y 100000?
Solución:
Para pensar en un problema, a veces es conveniente pensar en números más bajos, para entender qué sucede.
Vamos a rebajar la exigencia. En lugar de pedir 9 restos, vamos a conformarnos con 1.
En ese caso, lo que estamos buscando es un entero que de resto al dividirlo entre 2 distinto de cero. Vamos, un impar. El más pequeño es 1, y hay uno cada 2 unidades.
Subamos un poco. ¿Y si queremos que haya 2 restos?
Buscamos un entero que proporcione restos diferentes entre sí al dividirlo entre 2 y entre 3, y que tampoco valgan 0. Claro, al dividirlo entre 2 debe dar resto 1. Y al dividirlo entre 3 debe dar resto 2 (sólo puede ser 0, 1 o 2, y evidentemente no puede ser uno de los dos primeros). Observamos que 1, 2, 3, y 4 no valen, por lo que paramos en el 5, el primero válido. Si seguimos explorando, el siguiente es el 11. Cada 6 unidades hay uno, (17, 23, 29, …), siempre antes de un múltiplo de 2 y de 3. ¡Ahí está la clave!
Vamos a generalizar.
Si tenemos un entero de los requeridos en el problema, un entero piola, el resto al dividirlo entre 2 debe ser necesariamente 1, al dividirlo entre 3 debe ser necesariamente 2, y así, sucesivamente, al dividirlo entre cualquier número n entre 2 y 10, el resto debe ser n – 1, ya que los restos anteriores ya estarán usados, y no puede ser 0.
Por otra parte, si le sumamos 1, el resto al dividirlo entre esos números entre 2 y 10 pasaría a valer 0, es decir, se trataría de un múltiplo de todos ellos.
Es decir, que los enteros piola son anteriores a un múltiplo de todos los números entre 2 y 10.
Pero estos valores son múltiplos a su vez del mínimo común múltiplo, que sería 2³·3²·5·7 = 2520. El primero, como podemos comprobar, es el 2519, y cada 2520 unidades encontraremos otro.
Para saber con seguridad cuántos hay, basta dividir 100001 entre 2520, (sumamos 1 para cubrir el supuesto de que 100001 fuese múltiplo de 2520, que no es el caso), y como esta división entera es 39 ( y con resto 1720), el número total de enteros piola que nos piden será exactamente de 39 por debajo de 100000.
