Método del residuo chino para sistemas de congruencias
Una compañía de n soldados es tal que:
– n es un número capicúa. (Se lee igual al derecho y al revés. Ejemplo:15651, 9436349.)
– Si los soldados se forman de 3 en 3, quedan 2 soldados en la última fila; de 4 en 4, quedan 3 soldados en la última fila; de 5 en 5, quedan 5 soldados en la última fila.
Hallar el menor n que cumple las condiciones y demostrar que hay una infinidad de valores n que las satisfacen.
Solución
El problema se deja modelar con el sistema de congruencias siguiente:
Vamos a descomponer el problema en tres subproblemas, y al final sumamos las soluciones. En cada subproblema en que lo vamos a descomponer se busca un número tal que... bueno, mejor primero vean que el método funciona y saquen sus propias conclusiones sobre él:
Primer subproblema: encontrar un múltiplo de 12 (de 3 y de 4, los dos primeros módulos) que también sea múltiplo de 5.
Primer número=0 (si se escoge el 60 no hay problema, pero el cero es el menor positivo)
Segundo subproblema: encontrar un múltiplo de 20 (de 4 y de 5) que deje 2 al dividirlo entre 3.
Veamos... 20, 40,60, 80... (el 20 cumple y también el 80=3*26+2)
Segundo número=80 (el lector debería comprobar que con el 20 también funciona, es decir, con cualquiera que cumpla)
Tercer subproblema: encontrar un número múltiplo de 15 que deje 3 al dividirlo entre 4.
... 15, 30, 45, 60, 75, 90,... (el 15 cumple... )
Tercer número=15.
Solución sin considerar capicúa: n=0+80+15=95. El lector haría bien en verificar que 95 cumple el sistema de congruencias.
(Pero también cumplen todos los números de la forma n=95+60k, con k entero. Nótese que 60 es el producto de los módulos. Nótese también que n=35+60k es también solución general.)
Solución mínima sin considerar capicúa: n=35
Ver la solución completa en el problema Método chino del residuo
Nota: este problema es el 2 del concurso nacional de la OMM, 1991.
Los saluda
jmd
PD: El método usado arriba para resolver un sistema de congruencias está en la base de la demostración del teorema chino del residuo. Seguramente también se puede resolver con fuerza bruta pero cualquiera se desanima ante la perspectiva de probar la sucesión 5, 10, 15,... por sus residuos al dividir entre 4 y entre 3... si bien, la tenacidad del concursante se vería premiada en el intento 7 (35=5*7). Pero todavía faltaría ver que la solución general es de la forma n=95+60k... casi obligatoria para la segunda parte el problema...
