Certamen Urbana Metropolitana 2014 - Nivel 3 - P2

[Ignacio B]

Demostrar que en cualquier sucesión de [math]79 enteros positivos consecutivos hay uno de ellos cuya suma de dígitos es múltiplo de [math]13. Dar una sucesión de [math]78 enteros positivos consecutivos tales que ninguno tenga la suma de sus dígitos divisibles por [math]13.

[CarlPaul_153]

Spoiler: mostrar

Primero voy a demostrar que no puede haber [math]40 o mas números en la misma centena.
Supongamos que los hay, y que el primer numero de esa centena es [math]n=100x+10a+b.
Ahora, para esos [math]40 o mas números [math]x siempre será igual. Las decenas van a recorrer desde [math]a hasta [math]a+3 y [math]b cualquier número desde [math]0 a [math]9. En total son [math]13 números por lo tanto la suma de las cifras de esos [math]40 números recorren todos los restos en la división por [math]13. Absurdo.

Ahora voy a buscar un ejemplo con [math]39 números en una centena y [math]39 en otra. (es decir [math]78 números consecutivos).
Evidentemente la sucesión empieza con [math]n=100x+61. La suma de las cifras de [math]61 a [math]99 recorre todos los restos en la division por [math]13 excepto por el [math]6. la suma de las cifras de [math]00 a [math]38 recorre todos los restos en la división por [math]13 excepto el [math]12. Lo que voy a hacer es que en los primeros [math]39 números la suma de las cifras de [math]x tenga resto [math]7 en la división por [math]13 (ya que [math]7+6=13) y que en los últimos [math]39 números la suma de las cifras de [math]x tenga resto [math]1 en la división por [math]13. Una forma fácil de hallarlo es con [math]x=10^k -1. de donde [math]9k=13m+7. (corregido*) Aquí se puede usar teorema chino del resto o simplemente probar con los valores del [math]1 al [math]13 para [math]k. me queda [math]k=8 por lo que la sucesión va desde:
[math]9999999961 (ocho nueves) hasta [math]10000000038.

[JPablo]

Spoiler: mostrar

Primero voy a demostrar que no puede haber [math]40 o mas números en la misma centena.
Supongamos que los hay, y que el primer numero de esa centena es [math]n=100x+10a+b.
Ahora, para esos [math]40 o mas números [math]x siempre será igual. Las decenas van a recorrer desde [math]a hasta [math]a+3 y [math]b cualquier número desde [math]0 a [math]9. En total son [math]13 números por lo tanto la suma de las cifras de esos [math]40 números recorren todos los restos en la división por [math]13. Absurdo.

Ahora voy a buscar un ejemplo con [math]39 números en una centena y [math]39 en otra. (es decir [math]78 números consecutivos).
Evidentemente la sucesión empieza con [math]n=100x+61. La suma de las cifras de [math]61 a [math]99 recorre todos los restos en la division por [math]13 excepto por el [math]6. la suma de las cifras de [math]00 a [math]38 recorre todos los restos en la división por [math]13 excepto el [math]12. Lo que voy a hacer es que en los primeros [math]39 números [math]x tenga resto [math]7 en la división por [math]13 (ya que [math]7+6=13) y que en los últimos [math]39 números [math]x tenga resto [math]1 en la división por [math]13. Una forma fácil de hallarlo es con [math]x=10^k -1. de donde [math]10^k=13m+8. Aquí se puede usar teorema chino del resto o simplemente probar con los valores del [math]1 al [math]13 para [math]k. me queda [math]k=12 por lo que la sucesión va desde:
[math]9999999999961 (once nueves) hasta [math]10000000000038.

El ejemplo está mal:

Spoiler: mostrar

Si son once nueves, entonces en algún momento vas a tener el número [math]9999999999999 (trece nueves) cuya suma de dígitos es obviamente divisible por [math]13.

Un mejor ejemplo es [math]9999999961 (ocho nueves) como primer número de la sucesión de [math]78 enteros consecutivos.

[CarlPaul_153]

Muchísimas gracias! me ayudaste a darme cuenta que mi calculadora no arroja decimales si el número tiene 10 cifras 3 dias antes del regional
jaja efectivamente, ese es el resultado.
Resulta que estaba haciendo con x en vez de la suma de las cifras de x.

[JPablo]

Muchísimas gracias! me ayudaste a darme cuenta que mi calculadora no arroja decimales si el número tiene 10 cifras 3 dias antes del regional
jaja efectivamente, ese es el resultado.
Resulta que estaba haciendo con x en vez de la suma de las cifras de x.

No hay problema! Yo cometí exactamente el mismo error en el examen jajaja. Ahora bien:

Spoiler: mostrar

Podría ser ese resultado o bien, por ejemplo, [math]589999999961 porque [math]5+8=13, y eso no varía el resto en la división por [math]13 de la suma de dígitos.

[JPablo]

Pasó un tiempo y se me ocurrió volver a pensar este problema

Una forma un poco distinta de dar la sucesión:

Spoiler: mostrar

Para cada número natural [math]x, sea [math]S\left ( x \right ) la suma de sus dígitos. Diremos que un entero positivo [math]n es adecuado si y sólo si [math]S\left ( n \right )\not\equiv 0\pmod {13}. Veamos cómo formar una sucesión de enteros adecuados dentro de una misma centena.

Notemos que si [math]10\mid {n}, entonces si [math]n es el primer número de la sucesión, los primeros [math]10 números tendrán restos consecutivos módulo [math]13. Al pasar de una decena a otra, el resto disminuye en [math]8. Por lo tanto, la longitud máxima que podemos lograr es cuando [math]S\left ( n \right )\equiv 1\pmod {13}, de esta forma la sucesión de restos por decena sería

[math]1,2,3,4,5,6,7,8,9,10
[math]2,3,4,5,6,7,8,9,10,11
[math]3,4,5,6,7,8,9,10,11,12
[math]4,5,6,7,8,9,10,11,12

Y el siguiente número ya no sería adecuado. Esta sucesión tiene [math]39 números, por lo tanto, sabiendo ya que puede haber [math]39 números adecuados consecutivos en una decena, podemos buscar una centena cuyos últimos [math]39 números sean adecuados, tal que los primeros [math]39 números de la centena siguiente sean también adecuados. Con esto lograremos lo que queremos, ya que [math]39+39=78.

Pero entonces el primer número de la sucesión deberá terminar en [math]61, ya que entre [math]61 y [math]99 hay [math]99-61+1=39 enteros. Como ya vimos, podemos lograr una sucesión de [math]39 enteros consecutivos adecuados si el primero de ellos es el primero de una decena y la suma de sus dígitos es congruente con [math]1 módulo [math]13. Por lo tanto podemos establecer que la segunda centena (el número en la posición [math]40 de la sucesión) sea de la forma [math]10^k.

Ahora bien: el primero de todos no es el primer número de una decena, es el segundo (su unidad es [math]1). Sin embargo, aun así podemos hacer que el primer número de la sucesión tenga la suma de sus dígitos congruente con [math]1 módulo [math]13: la sucesión de restos por decena sería

[math]1,2,3,4,5,6,7,8,9
[math]1,2,3,4,5,6,7,8,9,10
[math]2,3,4,5,6,7,8,9,10,11
[math]3,4,5,6,7,8,9,10,11,12

Y como vemos, tenemos [math]39 números. Como la segunda centena será una potencia de [math]10, entonces el primer número de la sucesión será de la forma [math]\underset{x}{\underbrace{99\cdot \cdot \cdot 99}}61. Calculemos un posible valor de [math]x: La suma de los dígitos de este número es igual a [math]9x+6+1=9x+7. Nosotros queremos que [math]9x+7\equiv 1\pmod {13}\Longleftrightarrow 9x\equiv 72\pmod {13}. Como [math]13 y [math]9 son coprimos, es posible dividir la congruencia por [math]9, quedando finalmente [math]x\equiv 8\pmod {13}. Obviamente podemos tomar [math]x=8, de tal forma que el primer número de la sucesión vendría siendo [math]9999999961.

[JPablo]

Una pregunta... ¿Puede ser que no sea cierto que en una centena puede haber como máximo [math]39 enteros positivos consecutivos con suma de dígitos no divisible por [math]13? Porque me parece (no estoy seguro) que encontré un contraejemplo.

El contraejemplo que creo haber encontrado es la sucesión de enteros consecutivos desde [math]941 hasta [math]988 (que son [math]48 enteros consecutivos, todos en la misma centena). ¿Alguno podría verificar, a ver si no soy yo el boludo que hizo mal algo?

[Fran5]

No, está bien.. el único detalle es que si la extendés no llegás a los 78 del enunciado xD

Viste que vos antes hiciste la "tablita" de los restos, que te daba como máximo [math]39

[math]1,2,3,4,5,6,7,8,9,10
[math]2,3,4,5,6,7,8,9,10,11
[math]3,4,5,6,7,8,9,10,11,12
[math]4,5,6,7,8,9,10,11,12

Bueno, con el nuevo ejemplo, como que tenes una nueva tablita

[math]0,1,2,3,4,5,6,7,8,9
[math]1,2,3,4,5,6,7,8,9,10
[math]2,3,4,5,6,7,8,9,10,11
[math]4,5,6,7,8,9,10,11,12
[math]5,6,7,8,9,10,11,12,0

Que coincide con [math]S(n) desde [math]940 hasta [math]989

Lo importante es ver dónde aparecen los [math]0 en tu tablita, para poder cambiar de centena.
Lo que se demostró es que no puede haber más de [math]40 números consecutivos (que abarquen toda la decena) con suma no divisible por [math]13

[Gianni De Rico]

Una un poquito distinta:

Spoiler: mostrar

Como $4+9=13$, las sucesiones que comienzan en $\{1,2,3,4,5,6,7,8,9\}$ no funcionan, pues incluyen al $49$. Ya que la suma de las cifras de los números desciende en $8$ cada vez que cambian de decena, vamos a comenzar contando desde el primer número de cada decena (las decenas van desde $10k$ hasta $10k+9$ con $k\in \mathbb{Z}$ y $k\geq 0$). Supongamos que la suma de sus cifras tiene resto $x$ en módulo $13$, haciendo una tablita con los restos se llega a que el número $39$ de la sucesión tiene resto $x+11\pmod{13}$ y que el número $40$ tiene resto $x+12\pmod{13}$, ya que no cambia de decena, por lo que tenemos los restos desde $x$ hasta $x+12$, es decir, todos los restos posibles módulo $13$. Eso significa que no podemos poner más de $40$ números en cada centena. Si existiese una sucesión de $79$ números, tendrían que estar repartidos en dos centenas distintas, pero por Palomar una tendrá al menos $40$ números.

La sucesión la hice de la misma forma que los de arriba, así que no la escribo.