Tirando nueves al techo: la aritmética del reloj

Índice de los artículos


Cerramos el artículo anterior con una imagen de un «reloj» particular, diciendo que era un ejemplo de la herramienta que usaríamos para resolver todos los problemas. Veamos cómo.

El cálculo del resto de una división tiene mucho que ver con estos «relojes». Consideremos nuevamente el ejemplo 29 ÷ 8. Aquí sabemos que el cociente es 3 y el resto 5. De lo que vimos la vez pasada sabemos que la división por 8 solo puede dar ocho restos: 0, 1, 2, 3, 4, 5, 6, 7. Ahora bien, mira nuevamente nuestro «reloj»: en cada una de las «horas» tienes los posibles restos de la división por 8.

Comencemos a girar, una unidad cada vez, desde el cero y en sentido horario: del cero pasamos al 1 en el primer desplazamiento, al 2 en el segundo, al 3 en el tercero… al 7 en el séptimo, ¡y al cero en el octavo! Una vuelta completa son ocho desplazamientos, dos vueltas 16, tres vueltas 24, solo sobran 5 desplazamientos para llegar a los 29, ¡pero 5 era el resto de la división!

Vemos aquí un ejemplo de aritmética modular, un tema introducido por el mismísimo Gauss en 1801. No voy a entrar en los detalles (tampoco podría), pero básicamente estamos creando un «anillo» (o «reloj») de enteros consecutivos que incluyen el cero y que se recorre cíclicamente. Estos pequeños grupos permiten definir operaciones de suma y producto, lo que nos permite además establecer una equivalencia entre un número entero cualquiera y un número en el anillo: simplemente damos todas las vueltas necesarias y vemos dónde caemos. En nuestro caso, si tomas un anillo de ocho elementos (del cero al siete) y comienzas a girar para ver dónde cae un número cualquiera, obtendrás directamente el resto de la división entre ese número y 8.

Veamos ahora de dónde viene eso de «aritmética». Sabemos que 29 mod 8 es 5, podemos ver que 9 mod 8 es 1, ¿qué nos dará (29 + 9) mod 8? Pues sí, nos dará 5 + 1.

Pero atención: no podemos decir que el resto de una suma es la suma de los restos: 15 mod 8 da 6, pero (29 + 15) mod 8 no es 5 + 6 sino (5 + 6) mod 8 = 3.

En general, tenemos que si N mod k = n y M mod k = m:

(N + M) mod k = (n + m) mod k

En un «anillo de orden k» la suma de dos números es equivalente a la suma de los restos de la división de esos números por k.

Esto que es válido para la suma, también funciona para la resta… pero teniendo un poco de cuidado. Pregunta: ¿cuánto vale (–1) mod 8?

Puedes hacerte una idea intuitiva de la respuesta volviendo a nuestro reloj. Hasta ahora teníamos números positivos y girábamos siempre en sentido horario. Pues bien, con números negativos simplemente tenemos que hacer lo contrario: girar en sentido antihorario. Si en nuestro reloj de ocho elementos (del 0 al 7) partimos entonces del cero y nos desplazamos una unidad en sentido antihorario, ¡terminaremos en el 7!

Por lo tanto, si tenemos 29 mod 8 = 5 y 15 mod 8 = 7 tendremos que

(29 – 15) mod 8 = (5 – 7) mod 8 = (–2) mod 8 = 6

Y ahora sí podemos comenzar a resolver los problemas.

Empecemos por el final, con el problema que repito a continuación

Imagina que viene un matemático y te dice lo siguiente:

Elige 9 números enteros, los que quieras. Te apuesto que soy capaz de encontrar al menos dos de ellos cuya diferencia sea divisible por 8.

¿Aceptarías la apuesta?

Ahora ya deberías darte cuenta de que no te conviene: veamos el motivo.

Supongamos que has elegido nueve números, N₁, N₂, … , N₉. Calculemos ahora todos los rk = Nk mod 8 con k de 1 a 9. Como sabemos, solo podemos obtener ocho resultados posibles, pero al tener nueve números, al menos dos de estos nueve restos tendrán que ser iguales. Supongamos que Np mod 8 = Nq mod 8, ¡eso quiere decir que (Np – Nq) mod 8 = 0!

Nunca apuestes contra un matemático.

Los últimos dos problemas quedan para el próximo artículo.