Nadie sabe cómo lo hace, todos saben que sí lo hace. (Un slogan del alka seltzer de hace algunos años.) Este talante del slogan se puede aplicar muy bien a los algoritmos en matemáticas --cuando su eficacia queda comprobada en los resultados.
El slogan se puede ilustrar con el cebo o aceite de tacuache (ya se que el nombre correcto es tlacuache, pero así no se dice en Viento Libre): Una vez que alguien se deja convencer de que es eficaz y lo usa, queda maravillado (pues la tos desaparece como por arte de magia).
¿Es importante saber cómo lo hace? Bueno, lo cierto es que tampoco sabemos cómo lo hace el jarabe recetado por el médico. De poco nos sirve que nos expliquen que es antitusivo y mucolítico, con acción surfactante, ni tampoco que nos hayan mencionado sus ingredientes (dextrometorfano, ambroxol).
Pero tomemos un ejemplo de las matemáticas de concurso: la caja mágica (magic box). La caja mágica es una consecuencia del algoritmo extendido de Euclides. Como se sabe, el algoritmo de Euclides calcula el MCD de dos números enteros a y b, y es todo lo que hace --además de ser una herramienta teórica para demostrar algunos otros teoremas.
Pero si se lleva un registro de algunos resultados intermedios (ciertos coeficientes), el algoritmo de Euclides calcula también los coeficientes x,y que expresan el MCD como combinación lineal entera de los dos números a y b. A esta modificación o mejora del algoritmo de Euclides se le llama algoritmo extendido de Euclides. Y la caja mágica simplifica el algoritmo extendido de Euclides para su uso manual, es decir, para aplicarlo con lápiz y papel (o en el pizarrón).
Voy a presentar aquí una instancia de uso del método de la caja mágica (en el contexto de un problema de números) para calcular los coeficientes que hacen pósible expresar el máximo común divisor g de dos dos números a y b en
términos de éstos. Es decir como g=ax+by. ¿A quién le puede importar la caja mágica? Bueno, por lo pronto a los adolescentes que participan en concursos de matemáticas...
Instancia de uso de la caja mágica
Al dividir un número entre 3 deja residuo 2, al dividirlo entre 5 deja residuo 2, y al dividirlo entre 7 deja residuo 5. ¿Cuál puede ser ese número?
En términos de congruencias el problema se deja modelar mediante el siguiente sistema:
x=2(mod 3)
x=2(mod 5)
x=5(mod 7)
Como x-2 es múltiplo de 3 y 5, y estos dos números son coprimos, entonces x-2 es múltiplo de 15, digamos x-2=15k. Sustituyendo en la tercera ecuación de congruencias --puesta en la forma x-2=3(mod 7)-- se obtiene la ecuación de congruencias 15k=3(mod 7). Lo cual puede traducirse a 15k=3+7m, para m entero.
Pero 15k-3=3(5k-1)=7m. De aquí que 7 divide a 5k-1 (puesto que no divide a 3 pero sí a 3(5k-1)). Es decir, 5k-1 es múltiplo de 7. Y esto, expresado en congruencias, es 5k-1=0(mod 7). ¿Y cómo se resuelve una ecuación de congruencias como ésta?
Una forma es encontrando los multiplicadores k y m de la combinación lineal 5k+7m=1 (cambiamos el signo a la m para tener un 7 positivo). ¿Y cómo se encuentra esos multiplicadores?
Una forma es mediante la caja mágica que se ilustra a continuación (o bien por inspección):
7 1 0
5 0 1 1
2 1 -1 2
1 -2 3
(Explicación: el número a la derecha es el múltiplo de la fila que se resta de la fila de arriba para obtener la de abajo. El método para cuando se obtiene un 1 en la primera columna, y los multiplicadores son los restantes números de la fila.)
Los multiplicadores son entonces m=-2 y k=3, es decir, 5(3)+7(-2)=1. (La verdad no hacía falta ningún método para calcular los multiplicadores, pero no todos los problemas son así de fáciles.)
Ahora que ya encontramos la k podemos decir que el número x-2=15(3)=45. Comprobación: claramente 45 es múltiplo de 15 (de ahí lo calculamos) y, entre 7, deja 5 de residuo. Por lo tanto un posible número es x=47.
¿Y son todos los números posibles? Bueno, la respuesta es no. Porque podemos lograr el 1 de la siguiente manera (aprendan el truco): 5(3+7r)+7(-2-5r)=1 (porque las r se eliminan ¿no es cierto?).
Entonces los números posibles son de la forma x=2+15(3+7r)=47+105r. Es decir, son todos los números que dejan residuo 47 al dividir entre 105.
Otra instancia de uso
Encontrar los multiplicadores k y m en la ecuación diofantina 3k+7m=1 y todas las soluciones posibles.
7 1 0
3 0 1 2
1 1 -2 2
1 -2 5
Entonces los multiplicadores son -2 para el 7 y 5 para el 3. Es decir, 3(5)+7(-2)=1. Todas las soluciones se logran así: 3(5+7r)+7(-2-5r)=1. Esa decir, x=5+7r, y=-2-5r.
Problema
Resolver la ecuación diofantina 31x+21y=1770 para x,y enteros positivos.
Sugerencia: Resolver primero 31x+21y=1, después multiplicar las soluciones obtenidas por 1770 y, finalmente, encontrar todas las soluciones con el truco visto arriba y obligar la no negatividad.
Los saluda
jmd