TecnoXplora » CienciaXplora » Divulgación

MATEMÁTICAS EN VÍDEO CON AITOR MENTA

Los chinos dominarán hasta los restos (matemáticos)

Los chinos están por todas partes, son muchos y muy listos. Fijaos si lo son que ya en el siglo III Sun Tzu enunció una de los teoremas más interesantes para poder trabajar con números grandes

Sun Tzu es el padre del conocido como teorema chino de los restos, que se usa para operar con números grandes llevándolos a números pequeños. Se basa en jugar con las congruencias y asegura que si dividimos algo en paquetes de una cantidad N1, y después en paquetes de una cantidad N2 -y así de las formas que queramos, pudiendo sobrar algo siempre- siempre podemos determinar el número original. La única condición: esos N1, N2…  deben de ser primos entre sí.

Vamos a ver un ejemplo poniéndonos épicos y entrando en el universo de George RR Martin, el 'mata-héroes'. Imagina que en Desembarco del Rey tienen un tesoro y que todas las casas de los siete reinos quieren su parte.

Si eres fan de la saga sabrás que hay 15 casas. Imagina que en el primer reparto equitativo sobran 5 monedas de oro. No sabiendo cómo repartirse estas 5 monedas, se pelean y mueren los representantes de 8 casas como moscas. Ahora tendríamos 7 casas (primo de 15, y además coincide que también los Lannister son primos entre sí).

Resulta que siguen sobrando monedas de oro a repartir, esta vez 4. Se pelean a muerte y sobreviven -¡oh casualidad!- Solamente los Stark y los Lannister. Dos casas. Se deciden repartir todo y resulta que sobra una moneda de oro (y se la dan a Meñique, que es muy listo, como los chinos).

Pues como teníamos 15 casas, después 7 y después 2 casas, y 15, 2, y 7 son primos entre sí -es decir, no tienen divisores comunes- el teorema chino de los restos nos asegura que esto se puede resolver.

Por pasos

En el primer reparto había 15 casas y sobraron 3 monedas:

3 (mod 15), 3+15r

Después de la primera criba de George, tenemos

4 (mod 7) = 3+15r → r=1(mod 7)

Y en la última tenemos

1 (mod 2) = 1+7s

Reemplazando, podríamos calcular la solución de la ecuación:

123+210k

Por tanto, se estaban repartiendo un mínimo de 123 monedas de oro.

Los chinos saben mucho. Saben de restos, y de sumos (¿o eso eran los japoneses?)

Más sobre este tema: