El acertijo de hoy es uno de los problemas que publicó "El País" en 2011 con motivo del centenario de la Real Sociedad Matemática Española. Puedes consultar la lista completa AQUÍ.
Dado cualquier número natural, existe (y podemos encontrar) un múltiplo no nulo que esté compuesto únicamente por ceros y unos. Ese múltiplo, por supuesto, no tiene por qué ser único.
Por ejemplo, para los números del 1 al 7, los siquientes múltiplos cumplen esa propiedad de estar compuestos por ceros y unos:
1 * 1 = 1
2 * 5 = 10
3 * 37 = 111
4 * 25 = 100
5 * 2 = 10
6 * 185 = 1110
7 * 143 = 1001
2 * 5 = 10
3 * 37 = 111
4 * 25 = 100
5 * 2 = 10
6 * 185 = 1110
7 * 143 = 1001
¿Eres capaz de hallar un método general para encontrar uno de tales múltiplos sea cual sea el número del que partas? Puedes comprobar tu respuesta hallando un múltiplo de 18 que sólo contenga ceros y unos. Para leer la solución, pulsa el botón de más abajo (recuerda que, como en todos los posts, el botón únicamente aparecerá cuando haya pasado una semana de la publicación).
En este otro post, podrás encontrar una manera de programar este algoritmo en JavaScript, con su correspondiente herramienta interactiva para que la pruebes tú mismo.
SOLUCIÓN: ¿cuántos restos posibles puedes obtener al dividir un número cualquiera por 2? Si es par, el resto es 0; y, si es impar, el resto es 1. En otras palabras, hay 2 restos posibles. Y al dividir por 3, ¿cuántos restos distintos hay? Exacto, sólo 3: 0, 1 y 2. En general, al dividir por un número n, se pueden obtener n restos distintos: 0, 1,..., n-1.
¿De qué nos sirve esto? Paciencia, enseguida lo veremos... Para ilustrar la solución, resolvamos el problema propuesto para el número 18, aunque el método es válido para cualquier número.
Construye la secuencia de números 1, 11, 111, 1111,... hasta que llegues al número formado por 19 unos seguidos, por lo que tendrás 19 números en tu lista, cada uno con un uno más (en general, si nuestro número de partida es n, construimos la lista con n+1 números de esta forma).
Vamos a dividir cada uno de los elementos de la lista por 18 y anotaremos el resto de esa división. Comenzamos por 1, que trivialmente da un resto de 1. El número 11 también es trivial y su resto es 11. Para 111, obtenemos como resto 3, ya que 111 = 6*18 + 3. En cuanto a 1111, el resto es 13. Procedemos de esta manera hasta terminar nuestra lista de números.
¿Cuántos restos acabamos de escribir? 19. ¿Cuántos restos posibles hay al dividir por 18? 18. Es fácil ver que, al menos, dos de los restos que acabamos de obtener tienen que ser iguales. Identificamos cuáles son: en nuestro caso, 1111111111 (diez unos) y 1 dan como resto 1.
Si restamos estos dos números: 1111111111 - 1 = 1111111110, el resultado está formado únicamente por ceros y unos y es un múltiplo de 18, ya que hemos restado dos números cuyo resto era idéntico. Hemos encontrado lo que queríamos.
Esto de encontrar dos números formados por varios unos que tengan el mismo resto al dividir por n y restarlos, funciona en general, y siempre obtendremos un múltiplo de n que consiste en varios unos seguidos de varios ceros.
Si tan sólo nos hubiese interesado resolver este problema para el número 18 y no obtener el método general, podríamos haber tomado un camino muchísimo más sencillo. Cualquier múltiplo de 18 lo será también de 2 y de 9, obviamente. Entonces, buscamos un múltiplo de 2 que solo contiene ceros y unos. ¿Cuál será su última cifra? Está claro, ¿no? Tiene que ser un 0 (*). Además, por ser múltiplo de 9, la suma de sus cifras también será múltiplo de 9. Dado que solo disponemos de ceros y unos, para que sumen un múltiplo 9, sus cifras consistirán en un número múltiplo de 9 de unos y, el resto, ceros (**). El número más pequeño y simple que podemos construir de forma que se cumplan las condiciones (*) y (**) es el 1111111110, nueve unos seguidos de un cero, la misma respuesta a la que habíamos llegado siguiendo el método general.
El 61728395!
ResponderEliminarMuy bien, el 18*61728395 :D Qué rápido has sido!
Eliminar