Decimos que un número entero no-negativo $n$ contiene a otro número entero no-negativo $m$, si los dígitos de su expansión (o desarrollo) decimal aparecen en forma consecutiva en la expansión (o desarrollo) decimal de $n$. Por ejemplo 2016 contiene a 2,0,1,6, 20, 16, 201 y 2016. Determina el mayor número entero $n$ que no contiene a ningún múltiplo de 7.
Enlaces:
[1] https://www.matetam.com/print/problemas/combinatoria/multiplo-7-digitos-consecutivos#comment-3116
[2] https://www.matetam.com/problemas/combinatoria
[3] https://www.matetam.com/problemas/numeros
[4] https://www.matetam.com/categoria/nivel/intermedio
[5] https://www.matetam.com/problemas/categoria/olimpiada-mexicana-matematicas/xxx-omm-2016
Hola a todos. Voy a comentar [1]
Hola a todos.
Voy a comentar rápidamente la solución sin meterme en detalles de dónde surgen las ideas. La verdad no he encontrado por que sea natural considerar ciertos tipos de números que a continuación veremos. Después haré algunos comentarios sobre modificaciones al problema. Comentarios que se basan en la solución, por eso creo importante escribirla primero.
La solución.
Demostraremos que un número de 7 dígitos (y por tanto, de más) contiene un múltiplo de 7. Sea $N$ un entero positivo de 7 cifras. Y $a_k$ el número formado por las últimas $k$ cifras. Por ejemplo si $N=1234567$ entonces $a_3 = 567$. Entonces considera los números $a_1, a_2, \cdots , a_7$ si alguno es múltiplo de 7, acabamos. De otro modo, hay dos de ellos que dejan el mismo residuo módulo 7 (por principio de casillas). Digamos que son $a_l$ y $a_j$ con $j > l$. Entonces el número $a_j - a_l$ es, por un lado múltiplo de 7. Aunque también es el número contenido en $N$ desde la j-ésima cifra hasta la $l$-ésima cifra seguido de algunos ceros. Pero si 7 divide a un número que acaba en algunos ceros, también divide al número que no tiene esos ceros al final. Y se sigue.
La segunda parte del
La segunda parte del problema es probar que 999993 funciona y que los demás seis no.
Sólo hay un comentario que puedo hacer sobre las ideas de este problema. Y es que considerar los números $a_k$ sólo lo había visto una vez en un problema más o menos clásico y de hecho la conclusión es igual. '' Probar que cada número coprimo con 10 tiene un múltiplo compuesto por puros 1's". Este problema está por aquí en MaTeTaM.
Sobre el choque de la primera parte con la segunda.
La primera parte es limpia si bien es díficil de imaginar que saldrá así. Es muy bonito en realidad. Lo que pasa con la segunda es que, de tener mala suerte el número a buscar no podría estar cerca de 999999. Y sería muuuy complicado encontrarlo. Otra cosa es que no sale limpio. ¿Cómo probar que los otros seis no funcionan? Ya que el criterio del siete es díficil de aplicar. Y obligatorio será calcular los residuos de $10^k$ para suficientes valores de $k$.
Por esto, es mejor quedarse sólo con la primera parte. De por sí, tiene nivel nacional. Haciendo el comparativo con el problema de los puros 1s, se puede llegar a la siguiente generalización (tratando de quedarnos sólo con la primera parte):
" Muestra que para cada entero positivo $n$ coprimo con 10. Existe un entero positivo $N$ tal que todo número mayor a $N$ contiene un múltiplo de $n$. "
El cuál es un problema bastante fuerte. Que dista en díficultad del de los puros 1s. Pero tiene la misma solución que la primera parte del problema original. Tal vez se eligió el siete para dejar el problema menos abstracto. Pero es que, en lo personal haber agregado la segunda parte con el siete le agrega dificultad innecesaria al problema. En resumen había dos opciones:
Quiero platicar sobre esta segunda opción. ¿Cómo se escogería dicho $n$? Bueno, sea $M_n$ la respuesta para dicho entero positivo. Por ejemplo $M_7 = 999993$. No sé si haya una manera rápida de llegar a $M_n$ cuándo se toma un $n$ arbitrario. Podría estar muy separado de $10^{n-1}$ (que es la cota). Veamos los primeros valores de $n$. Si n=3 es trivial. Si n=7 obtenemos el problema original que si bien no es un trabajo titanico argumentar rigurosamente la segunda parte, tampoco esta muy padre. Con n=9 obtenemos una buena opción pues el criterio del 9 es fácil de aplicar. Pero mucho más fácil que eso: Si el número contiene un nueve o cero en su expansión, acabamos. Como se trabaja con números consecutivos digamos $M_9 , M_9 + 1, \cdots, 10^{8}$ se puede esperar que si un número contiene un 9. El siguiente o bien contenga ese mismo nueve o un cero. Para $n=9$ la segunda parte se reduce a
" Muestra que cada número entre 888888 y 100000000 contiene un nueve"
Lo cual, me parece interesante. Pero también me agradaría saber otras opiniones. ¿A tí que versión te gusta más?
Cordialmente,
germán.
El siguiente argumento
El siguiente argumento evita el uso de congruencias para la segunda parte del problema. Termina por convencerme de que es un gran problema.
(1) Tenemos que ver que cada número entre 999994 y 999999 contiene un múltiplo de 7. (2) Por otra parte tenemos que demostrar que 999993 no contiene ninguno
Notemos que 7 | 98. Luego $10 \cdot 98 + 14=994$ es múltiplo de 7. Lo que implica que $10\cdot994 + 56 = 9996$ es múltiplo de 7. Usando este argumento se justifica que 99995 y 999999 son múltiplos de 7. Esta lista de números justifican ambas cosas que necesitabamos. (1) por obvias razones y (2) por que nos dice que el primer múltiplo de 7 que comienza con nueves es 999999. Y nunca aparece en esta lista algo del estilo 99...93. Aunque este es fácil descartarlo pues de ser múltiplo de 7. Se tendría que 99...93 + 7 = 10...0 también lo es.
Cordialmente,
germán.