Sea n un número natural cualquiera; si tomamos los n+1 naturales siguientes, formados sólo por unos:
Atila, rey de los Hunos (con H)
(léase «a sub 1, a sub 2…»)
a1=1 ; a2=11 ; a3=111 ; … ; an=111…(n)…1 ; a(n+1)=111…(n+1)…1
y consideramos los restos de estos n+1 números al dividirlos entre n,
Nadal al resto, en nuestro caso en Zn
Por ejemplo, si consideramos n=6, tomaríamos los 7 siguientes números:
1, 11, 111, 1111, 11111, 111111, 1111111, cuyos restos al dividirlos por 6 (es decir, sus representantes en Z6) son respectivamente:
1, 5, 3, 1, 5, 3, 1
por el Principio del Palomar o de Dirichlet, está garantizado que al menos dos de esos restos han de ser iguales.
Si m palomas ocupan n nidos y m > n, entonces al menos un nido tiene dos o más palomas en él.
Sean p y q esos dos restos iguales (p<q), entonces, por definición, p y q son congruentes módulo n y queda garantizado que (q-p) es un múltiplo de n. Pero ese número (q-p), por la naturaleza de los ai definidos anteriormente, sólo está formado por unos y ceros. (q.e.d)
en nuestro ejemplo, el conjunto cociente Z6 ={[0], [1], [2], [3], [4]. [5]} tiene seis clases de congruencia módulo 6, pero como tenemos 7 restos, está garantizado que al menos dos se repiten, de hecho, como hemos comprobado hay más repeticiones. Por ejemplo si hallamos la diferencia a5-a2 (ambos valen 5 en Z6) obtenemos: 11111-11=11100=1850·6.
Asimismo encontraríamos como múltiplos el 1110, el 1111110, el 1110000, el 111000…
Santiprofemates 
Esta semana (y en las venideras haré lo mismo) no he guardado comentarios para publicarlos después. Os invito a que los publiquéis vosotros mismos ya sin censura ninguna (supongo que tendréis una copia, al menos en «enviados» del correo electrónico).
Saludos a todos y gracias de nuevo por vuestras aportaciones.
Despues de ver la solución, sé que nunca hubiese llegado a descubrirla.
Sinceramente… ¿Hay alguien que haya llegado a la solución sin haberla conocido, sin haberla buscado y sin que nadie se la haya dicho?.
Si es así… mi felicitación a esa persona.
Con un vocabulario menos elaborado, pero esa fue también mi respuesta.
Ahora bien, me echaron una manita, sólo no creo que se me hubiese ocurrido.
Desde que me incorporé a los retos, el tercero creo que era, me parece el más difícil; a pesar de que la respuesta es muy sencilla de entender.
No sabía lo que era el principio del palomar. Cuando comentastéis lo de las palomas, ya lo tenía resuelto. Lo había aplicado simplemente por lógica. Ya me he documentado y algo más hemos aprendido.
Quien me ayudó no me lo comentó, me orientó a trabajar solamente con unos, porque alguna operación ente ellos me llevaría a la respuesta.
Muy buenos e ingeniosos los pies de las fotos, Santi :-)
En mi caso no copio mi solución porque es idéntica a esta tuya, o a la de Ana publicada al final del post anterior. Además, teniendo en cuenta que el 99% del mérito de que lo solucionara es gracias a vuestra ayuda, me parece mejor que sean otras las que aparezcan.
Una preguntilla: una vez resuelto el misterio de las palomas, los (H)unos y el resto de Nadal… aún queda un «misterio sin resolver», como diría Fríker Jimenez: en algún comentario del post en el que se planteaba el problema se decía que uno de los ejemplos que se ponían en el vídeo del problema tenía trampa,y tú decías que no era uno, sino dos… ¿a qué os referíais con «trampa»?
Gracias como siempre, esta vez, más que nunca, sin este blog habría sido imposible.
A que esta demostración sólo sirve para números con todos los ceros al final, no en el medio
Gracias, era lo que suponía, lo que pasa es que ahora estoy en el trabajo, tengo el acceso a los vídeos «capado» y no podía confirmarlo.
Javier, en mi caso, sin la confirmación explícita por parte de Santi de que el principio de Dirichlet era básico en el razonamiento no lo habría demostrado ni en mil años. Una vez tuve esa confirmación, buceando en internet, encontré varios ejemplos «prácticos» de la aplicación de dicho principio («demostrar que si una persona se toma un total de 45 pastillas en un mes de 30 días, hay por lo menos una serie de días consecutivos en los que se toma exactamente 14 pastillas»), y a partir de ellos, generalizarlo para este problema se me hizo mucho más fácil.
Pero, lo dicho: sin esa pista, nuuuuunca hubiera llegado. Para mí, quitando el segundo (el de la hormiga), el desafío más difícil.
Pues en mi caso ni con las ayudas.
Entendí la pista de los H-unos, y también el principio del palomar, nunca entendí la pista del tenis. Estoy convencido que nunca jamás llegaría por mi cuenta a la ocurrencia clave.
Desde aqui te felicito, si con tan sólo esos datos, fuiste capaz de llegar a la demostración. Igualmente felicito a todos aquellos que tuvieron la genial idea. Y para terminar felicito igualmente a Santi por la elaboración de este blog que día a día está ganando en dinamismo y fuerza.
Muchas gracias Javier, por la parte que me toca.
Gracias, Javier, pero, repito, mi mérito en este caso es únicamente del 1%. Lo digo una vez más: hasta que Santi no me confirmó que el Principio del Palomar era el camino a seguir y me centré obcecadamente en él, estaba completamente perdido (de hecho, lo dije en uno de mis posts, algo así como: «por palomas sólo me sale el principio de Dirichlet, pero no le encuentro aplicación al caso»). Fue una pura cuestión de suerte: ambos, tú y yo, estábamos en el mismo punto, con Dirichlet en la mano y sin saber cómo seguir. Tú tuviste la «mala suerte» de que tu búsqueda googleiana sólo te llevó a la anécdota del número de pelos en la cabeza de los madrileños, y yo tuve sólo un poco más de suerte, sólo eso, suerte, de que, aparte de eso, también encontré algún ejemplo, alguna aplicación práctica reveladora que me hizo «ver la luz» y generalizar el principio del palomar a esta situación. Si tú hubieras tenido la chiripa de dar con las mismas webs con los mismos ejemplos explicados que yo, lo habrías solucionado fijo :-)
Este desafio está dentro de mis conocimiento matemáticos… tampoco es tan dificil de entender, pero la ocurrencia para llegar a la demostración está fuera de mi capacidad…
Debo catalogar esta demostración de genial.
¡Es muy bonita!.
Siguiendo la misma demostración también puedo decir que dado cualquier número debe existir otro cuya multiplicación de como resultado otro número formado por 2 y 0…, 3 y 0… etc.
Santi, la demostración, aparte de clara y sencilla, te ha quedado muy bien ilustrada.
A quien no lo haya acertado, ya le comento que yo necesité ayuda. Me di cuenta pronto de que este reto me superaba.
Por otro lado mi enhorabuena a los que hayan acertado sin ayudas.
Como dije en su momento, sencillo de explicar y comprender, pero muy difícil de resolver.
Gracias, aunque las pistas como siempre son cosa tuya. ;-)
Hola,
la solucion que dais es muy elegante, ahora yo no la conocia y no
encontre esta. Pongo mi solucion aqui abajo para que me digais si esta bien o no.
Sea A un numero natural cualquiera, cuyos digitos empezando
por las unidades son a0 a1 a2 a3 …
Queremos encontrar K, digitos k0 k1 k2 …, tal que K*A se
escribe solo con unos y ceros.
La clave esta en las unidades, a0, vamos a simplicar el problema:
1) Si a0 es 0 podemos quitarlo sin afectar la K final
2) Si a0 es 5 podemos multiplicar por 2 y recuperar la K inicial facilmente: (A*2)*K=A*(2*K)
3) Si a0 es par podemos multiplicar por 5.
Aplicamos 1) 2) y 3) hasta que a0 sea impar diferente de 5, osea, 1,3,7,9.
Inspeccionando las tablas de multiplicar de estos impares se comprueba que
las unidades de los productos nunca se repiten en la misma tabla. Los 10 digitos
de las unidades de cada tabla son los diez digitos que existen.
Multiplicando como en el cole, empezando por las unidades:
a0*k0 % 10 ha de ser 1 (0 no es interesante, solo alarga el problema)
(donde %10 quiere decir operacion modulo 10, el resto de dividir a0*k0 entre 10)
como a0 es 1,3,7 o 9, k0 solo tiene una solucion (las unidades nunca se repiten).
Las decenas:
(a0*k1 + a1k0 + (a0k0-1)/10) % 10 = 1 o 0
k0 ya esta definido, asi que esta ecuacion no es mas que
(a0*k1 + M) % 10 = 1 o 0
siendo M natural definido por k0, a0 y a1.
Asi pues esta ecuacion tiene 2 soluciones pues el resultado puede ser 1 o 0
y recordamos que la tabla de a0 no repite unidades.
En principio podemos coger cualquiera de las soluciones, pero como veremos
es importante coger k1 diferente de k0.
Las centenas y mas alla siempre se reducen a la misma ecuacion:
(a0*kn+M’) % 10 = 1 o 0
Siempre hay solution para kn, pararemos cuando A*K tenga solo unos y ceros,
esto debe cumplirse para alguna n ya que nos aseguramos de no caer en repeticiones
infinitas (pues hay siempre 2 soluciones).
Hola Rogelio, ahora tengo el tiempo justo para publicarlo, luego lo comento.
Saludos.
Pues sí, imagino que serás uno de esos de los que habla El País, que lo lograron a base de multiplicaciones… muy bien.
Hola, soy nueva en los comentarios aunque sigo el blog por los problemas del país desde hace tiempo.
Mi solución tiene que ver con el teorema de Euler-Fermat para restos potenciales. He dividido los números naturales en tres grupos: los que tienen por factores primos sólo el 2 y o el 5 , los que tienen el 2 o y el 5 y otros y los que no tienen ni a 2 ni a 5.
El primer grupo es evidente que tiene un múltiplo de esas características , el tercero por ser primo el número con las potencias de 10 , dividiendo éstas por el número obtenemos los restos potenciales que son periódicos y entre ellos está el 1 . Si sumamos las potencias de 10 que dan de resto 1 hasta obtener el número que sea conseguimos el múltiplo buscado.
Ejemplo: 7 ,podemos obtener el múltiplo 10^0+10^6+10^12+10^18+10^24+10^30+10^36.
Para el tercer grupo el mútiplo buscado es el producto del obtenido en el caso anterior por el del primer caso .Ejemplo: 35=7.5
10.(10^0+10^6+10^12+10^18+10^24+10^30+10^36)
Puede haber múltiplos más sencillos pero este es el caso general.
Perdón por ser tan escueta pero no he podido volcar mi demostración completa.
Ok, muchas gracias por tu aportación y bienvenida!
En el Pais dicen:
«Algunos lectores han enviado soluciones basadas directamente en la tabla de multiplicar y en ir encontrando una a una las cifras del número por el que hay que multiplicar N. Como ellos mismos han comprobado, dar esa demostración con todos los detalles es costoso. Aun así algunos lo han conseguido,…»
Espero ser uno de los que lo han conseguido, si no estaria bien saber cual es el razonamiento correcto usando este procedimiento, eso si, reconociendo que es mucho mas arduo…
Hola a todos.
Primero de todo reconocer que este Desafío superaba con creces mis conocimientos matemáticos. Yo, primero, había desarrollado una respuesta como la tuya, Rogelio, basándome en como nos enseñaron a multiplicar. Pero comprobé que no tenía nada que ver con lo que los demás compañeros iban aportando. Me centré luego en estudiar como ocurría el fenómeno y descubrí cosas curiosísimas que ya os conté un poco en un comentario (por ejemplo descubrí los que yo llamaba números «primos hermanos»). Pero volví a ver que no tenía nada que ver con lo que los demás estábais haciendo. Recogí la pista del palomar, recogí una gran pista de Pipín sobre un ejercicio en la Olimpiada Matemática, pero he sido incapaz de aplicarlo en este caso.
Finalmente decidí, por primera vez desde que empezó el juego, no enviar respuesta. Pero, como siempre me lo he pasado muy bien y os agradezco a todos las ayudas, los comentarios y el vicio que le ponemos entre todos. Especialmente a Santi, claro, que siempre está ahí.
¡Hasta el próximo!
Hasta el próximo pues Toni. Un saludo y gracias.
Santi, Toni, gracias por vuestros comentarios.
Me ha encantado este problema (junto con el de la hormiga, los mejores), me sorprendio la tan elegante solucion.
Saludos y, como dice Santi, hasta el proximo.
Cuando resolví el problema similar de la olimpiada matemática, lo hice con el teorema de Fermat. Luego, en la solución oficial, vi que se hacía con lo del Palomar y me pareció que jamás lo habría descubierto.
Lo de las fracciones generatrices sólo me sirvió como pista para llegar a los nueves y eso… por eso me ha dado un poco de rabia no haber llegado a la brillante demostración de Maider Goñi, a la que le habría dado el premio directamente por haber usado sólo conocimientos de EGB.
Pues tienes razón, podían dar premio a la demostración más sencilla de la semana…