El cocinero chino: un problema diofantino

Versión para impresión

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.