Solución del problema de marzo, 2007

El problema:
	Probar que hay infinitos enteros tales que (i) el número es divisible por la suma de sus dígitos (ii) ninguno de sus dígitos es cero.

Respuestas correctas:

Recibimos respuestas correctas de  Mohamed Benchaib (Marruecos) Matthew Lim (USA) Gérard Billion (France) Jean-Luc Luyet (Suiza) Lou Cairoli (USA) Mark Pilloff (USA) Dan Dima (Rumania) Joseph Najnudel (Francia) Philippe Fondanaiche (Francia) Ananda Raidu (India) Zac Friggstad (Edmonton) John T. Robinson (USA) Xavier Hecquet (Francia) K. Sengupta (India) Wolfgang Kais (Alemania) Heri Setiyawan (Indonesia) Normand LaLiberté (Ontario)

La solución:

El problema de este mes apareció como problema 3 en la Olimpíada Canadiense de Matemática de 1984.

Como hay reglas simples de divisibilidad para potencias de 2 y 5, y para múltiplos adecuados de 3 y 9, las soluciones recibidas se basaron en estas reglas. La aproximación más común en las soluciones recibidas, que fue también la usada en las soluciones oficiales a la OMC de 1984, es comenzar con cualquier número que satisfaga dos de las condiciones, como n = 1 o n = 12, y formar un número con 3 veces la cantidad de dígitos concatenando tres copias del número inicial.  En nuestros ejemplos obtenemos 111 o 121212. Entonces uno observa que el nuevo número es divisible por la suma de sus dígitos, que equivale a tres veces la suma de los dígitos del número original (en nuestros ejemplos, 3 = 3·1 o 9 = 3·(1+2)).  He aquí nuestro algoritmo en mayor detalle:

Sea n un número divisible por la suma de sus dígitos, ninguno de los cuales es 0, y sea d el número de dígitos (en la representación decimal de n), y s la suma de esos d dígitos.
Entonces el número n(10^2d + 10^d + 1) es divisible por 3s, ya que

1. 10^2d + 10^d + 1 (= 100...100...1) es divisible por 3 (recordemos que 3 divide a un número si y solo si divide a la suma de sus dígitos, que en este caso es 3), y
2. n es divisible por s (por definición de n). Observamos que n(10^2d + 10^d + 1) es el número que consiste en el número n repetido 3 veces, de manera que la suma de sus dígitos es 3s. Este proceso puede repetirse ad infinitum. 

           
En nuestro ejemplo comenzando con el número n = 12, d = 2 y s = 3. El siguiente número en la sucesión es 12(10⁴ + 10² +1) = 12(10101) = 121212, que es divisible por la suma de sus dígitos, 3·3 = 9. El siguiente número es 121212(10¹² + 10⁶ + 1) = 121212...12 (nueve 12's), que es divisible por 3·9 = 27. Y así sucesivamente. La sucesión que comienza con n = 1 es más fácil de estudiar: 1, 111, 111111111, ... ; el k-ésimo término de la sucesión, comenzando con k = 0, tiene 3 unos.

Generalización de Matthew Lim.
El argumento anterior funciona para cualquier base b siempre que b > 2. En lugar de usar 3 copias del número inicial, uno usa d copias, done d es cualquier divisor de b – 1. Lim muestra que si la suma de los dígitos del número inicial en su representación en base b es s, entonces d^k copias del número inicial tiene como suma de sus dígitos s·d^k , que divide al número. Luego da una agradable demostración de que b = 2 es una excepción genuina: cualquier número en base 2 sin ningún cero es necesariamente una cadena de unos, o sea 2^k – 1. La suma de los dígitos de 2^k – 1 es k, pero con un poco de teoría de números se puede probar que ningún k > 1 divide a 2^k – 1.

La sucesión de Jean-Luc Luyet.
Luyet fue el único en mostrar una sucesión infinita basada en la regla de que un entero es divisible por 2ⁿ si y solo si el número formado por sus últimos n dígitos es divisible por 2ⁿ. El plan básico es usar los números cuyos últimos n dígitos forman un múltiplo de 2ⁿ, luego agregar suficientes unos (u otros números) a la izquierda para que la suma de los dígitos sea 2ⁿ. La única complicación es asegurarse de que ninguno de los dígitos usados es cero. Como ninguna potencia de 2 termina en cero, podemos sumar múltiplos de 2ⁿ para librarnos de los ceros no deseados. Por ejemplo, para ser divisible por 2⁴ = 16, necesitamos que los últimos cuatro dígitos de nuestro número sean divisibles por 16. Entonces sumamos 100·16 + 16 = 1616 y tenemos nuestros cuatro dígitos finales no cero. Ahora queremos un número tal que la suma de los dígitos sea 16, y usamos 21616 (ó  111616). Otro ejemplo: para 32 podemos sumar 1000·32 + 100·32 + 32 = 35232 para obtener los últimos cinco dígitos, luego adjuntar 89 a la izquierda para obtener 8935232, que es divisible por la suma de sus dígitos, 32. En general, si el cero más a la derecha está en la posición 10^k, usamos 2ⁿ + 10^k·2ⁿ para eliminarlo. Continuamos sumando múltiplos adecuados de 2n — lo que siempre es posible porque el dígitos final de 2ⁿ nunca es cero — hasta que los últimos n dígitos a la derecha forman un número que es múltiplo de 2ⁿ, con ningún dígito igual a cero.