El enunciado del siguiente problema es clásico. El problema se denomina "el cocinero chino". Se usa para ilustrar el teorema chino del residuo. Me apresuro a aclarar que cualquier parecido con nuestra realidad humana es una ilusión óptica de los pesimistas --a menos que su realidad sea demasiado humana...:
Diecisiete piratas se reparten un botín de n monedas de oro. Acordaron partes iguales y, si hubiese un resto, se lo darían al cocinero chino. Después del reparto el chino recibió 3 monedas. Pero en la borrachera nocturna 6 piratas murieron acuchillados --en la riña acostumbrada en esos casos. Al otro día los sobrevivientes se vuelven a repartir las monedas y al cocinero le tocaron 4 monedas. Posteriormente, en un naufragio, sólo se salvó el botín, el cocinero y 6 piratas. Así que se vuelven a repartir y le tocaron 5 monedas al cocinero. Encontrar el número n de monedas con que se quedó el cocinero (como mínimo) después de envenenar a los piratas restantes (con un delicioso chou main cantonés con pollo). R. 785.
Solución
Como el lector debería saber, se tiene que resolver el sistema de congruencias
n=3(mod17)
n=4(mod11)
n=5(mod6)
Vamos primero a resolverlo sin usar directamente el algoritmo que se desprende de la demostración del teorema chino del residuo. Las dos primeras ecuaciones de congruencias pueden ser planteadas de la siguiente manera: n=17r+3=11s+4. Utilizaremos el método de las ecuaciones diofantinas para resolver este sistema.
La ecuación diofantina 17r+3=11s+4 puede transformarse a 11s=17r−1. Entonces s=r+(6r−1)/11, y para que s resulte entero es claro que x=(6r−1)/11 debe ser entero. Y si x va a ser entero, entonces r=(11x+1)/6=x+(5x+1)/6 debe ser también entero. Pero, para ello, y=(5x+1)/6 debe ser entero. Es decir, x=(6y−1)/5=y+(y−1)/5. De aquí que z=(y−1)/5 tiene que ser entero. De nuevo, se sigue que y=5z+1 debe ser entero. Pero esto se cumple simplemente con tomar z entero.
Ahora nos regresamos hasta poner r o s en términos de z. Entonces, x=5z+1+z=6z+1. Y, de aquí, r=x+y=6z+1+5z+1=11z+2. Por lo tanto, un n que satisface las dos primeras condiciones es n=17(11z+2)+3=187z+37. (Notemos que al dividir este n entre 17 deja 3 de residuo y si lo dividimos entre 11 deja 4.) Pero falta considerar la tercera condición.
Para ello resolvemos el sistema compuesto de esta ecuación recién lograda y la correspondiente a la tercera condición. Y el sistema se reduce a resolver la ecuación diofantina n=187r+37=6s+5, la cual podemos poner como 6s=187r+32.
Y de nuevo aplicamos el método diofantino: s=31r+5+(r+2)/6 y, como x=(r+2)/6 debe ser entero, r=6x−2; y ya está, pues basta con tomar x entero para que r sea entero.
Ahora, de regreso, ponemos n en términos de x: n=187r+37=187(6x−2)+37=1122x−374+37 =1122x−337. El lector puede verificar que esta ecuación cumple con las tres condiciones.
Así que si tomamos x=1, el cocinero chino se quedó con --por lo menos-- 785 monedas de oro. (Y podríamos terminar el relato a la manera de los Tigres del Norte: "...de las monedas y el chino, nunca más se supo nada...")
Los saluda
jmd
Ver más sobre el tema en http://ybonnet.free.fr/tipe/tipe-th-restes-chinois.doc
PD: El teorema chino del residuo lo abordaremos en un próximo post; tiene actualidad local, pues el problema 6 (el difícil) del examen final puede resolverse con el algoritmo a que da lugar la demostración de ese famoso teorema --o bien con el método diofantino explicado arriba.