Unos, ceros... y palomas

Nota importante: El desaf¨ªo de esta semana queda aplazado al viernes

Ya hay soluci¨®n para el decimoquinto desaf¨ªo matem¨¢tico con el que EL PA?S celebra el centenario de la Real Sociedad Matem¨¢tica Espa?ola. El profesor Jes¨²s Gago, de la Universidad de Sevilla, plante¨® el problema (v¨ªdeo de la izquierda) y ahora lo resuelven (v¨ªdeo de la derecha).

Recordemos que esta semana hab¨ªa que demostrar que dado un n¨²mero natural cualquiera siempre tendr¨¢ al menos un m¨²ltiplo no nulo formado por unos y ceros. Se han recibido 370 respuestas, de las que un 74% son correctas. Por el reducido n¨²mero de soluciones recibidas parece que no ha resultado un problema f¨¢cil, pero a muchos de nuestros lectores les ha servido para descubrir el Principio del Palomar, lo que nos alegra, aunque tambi¨¦n hay soluciones que utilizan correctamente dicho principio sin saberlo. Realizado el sorteo entre los acertantes el agraciado con una biblioteca matem¨¢tica como la que puede coleccionarse cada domingo con EL PA?S ha sido Carlos Segura Otero, de Mollet del Vall¨¨s (Barcelona). Esta semana en el quiosco, por 9,95 euros con el peri¨®dico, La burla de los sentidos, por Francisco Mart¨ªn Casadelrrey.

La soluci¨®n m¨¢s breve es la siguiente: dado un n¨²mero natural N, al dividir cualquier n¨²mero natural entre N s¨®lo se pueden obtener N restos distintos: 0, 1, 2,..., N-1. Por tanto, si consideramos N+1 n¨²meros de la forma 1, 11, 111, 1111, 11111,..., necesariamente hay dos que dan el mismo resto al dividir entre N (?esto es el Principio del Palomar!), y su diferencia es un m¨²ltiplo de N. Esta diferencia (restando el menor del mayor) la forman unos cuantos unos seguidos de unos cuantos ceros, con lo que hemos resuelto el desaf¨ªo. ?sta es la demostraci¨®n que ha dado ganador del sorteo.

Una segunda soluci¨®n, que tambi¨¦n ilustra el Principio del Palomar, es la enviada, entre otros, por Fernando Holgado (el residuo m¨®dulo N es otra forma de llamar al resto al dividir entre N):

Sea N el n¨²mero natural del que queremos hallar un m¨²ltiplo cuyas cifras son ceros y unos. Consideramos todas las potencias de 10 y vamos calculando sus residuos m¨®dulo N. Si alguno de ellos es cero, esa potencia de 10 ser¨¢ un m¨²ltiplo de N y ya tendr¨ªamos un m¨²ltiplo formado por unos y cero . Si ninguna de ellas da resto 0, tendr¨¢ que haber un momento en que se repita el resto que se obtiene (s¨®lo hay N restos distintos posibles). Es decir, 10^a=10^(a+h) m¨®dulo N. Y por tanto, 10^a=10^(a+h)=10^(a+2h)=10^(a+mh) m¨®dulo N para cualquier m mayor o igual que 1 [algunos lectores han sustituido este argumento por la observaci¨®n de que, al estar considerando infinitas potencias de 10 y ser los posibles restos un n¨²mero finito, al menos uno de ellos debe repetirse infinitas veces]. Si denotamos 10^a=r m¨®dulo 10, se tendr¨¢ que

10^a+10^(a+h)+10^(a+2h)+...+10^(a+(N-1)h)=r+r+r+...+r=Nr=0 m¨®dulo N, es decir, el n¨²mero indicado es un m¨²ltiplo de N, que al ser una suma de potencias de 10, estar¨¢ formado exclusivamente por unos y ceros.

Hemos recibido un tercer tipo de soluci¨®n, quiz¨¢s incluso m¨¢s elemental, que se basa en escribir la expansi¨®n decimal de 1/N. La versi¨®n m¨¢s sencilla de este argumento la ha dado Maider Go?i Urreta, que considera en realidad la expansi¨®n decimal de 1/(9N), observar que es finita o peri¨®dica y recuerda que, en cualquier caso, se puede escribir como una fracci¨®n con denominador bien 10^k formado bien formado s¨®lo por nueves y ceros. A partir de aqu¨ª se ve que ese denominador es un m¨²ltiplo de 9N y, para acabar, basta con dividir por 9 si fuese necesario.

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, y esperamos que sean precisamente ellos quienes m¨¢s aprecien el valor del Principio del Palomar.

Queremos comentar por ¨²ltimo que se han recibido soluciones que, antes de usar el Principio del Palomar, invocaban el Teorema de Euler-Fermat. Por supuesto son correctas, pero esta vez, y sin que sirva de precedente, usar "m¨¢s matem¨¢ticas" alargaba la soluci¨®n.

El viernes presentaremos un nuevo desaf¨ªo.

Unos, ceros... y palomas

Una cuesti¨®n de unos y ceros