El mono y los cocos

El espacio de búsqueda se puede reducir mediante una serie de factores cada vez mayores, observando la estructura del problema, de modo que, mediante un método de ensayo y error, se encuentre la solución. El espacio de búsqueda es mucho menor si se parte del número de cocos que recibió cada hombre en la división matutina, ya que ese número es mucho menor que el número en la pila original.

Si F es el número de cocos que recibe cada marinero en la división final de la mañana, la pila de la mañana es 5 F , que también debe ser divisible por 4, ya que el último marinero de la noche combinó 4 pilas para la división de la mañana. Así que la pila de la mañana, llamemos al número n , es un múltiplo de 20. La pila antes de que el último marinero se despertara debe haber sido 5/4( n )+1. Si solo un marinero se despertó en la noche, entonces 5/4(20)+1 = 26 funciona para el número mínimo de cocos en la pila original. Pero si dos marineros se despertaron, 26 no es divisible por 4, así que la pila de la mañana debe ser algún múltiplo de 20 que dé como resultado una pila divisible por 4 antes de que el último marinero se despierte. Da la casualidad de que 3*20=60 funciona para dos marineros: aplicando la fórmula de recursión para n dos veces se obtiene 96 como el número más pequeño de cocos en la pila original. 96 es divisible por 4 una vez más, así que para 3 marineros despertando, la pila podría haber sido de 121 cocos. Pero 121 no es divisible por 4, así que para 4 marineros despertando, hay que hacer otro salto. En este punto, la analogía se vuelve obtusa, porque para acomodar a 4 marineros despertando, la pila matutina debe ser algún múltiplo de 60: si uno es persistente, puede descubrirse que 17*60=1020 hace el truco y el número mínimo en la pila original sería 2496. Una última iteración sobre 2496 para 5 marineros despertando, es decir 5/4(2496)+1 lleva la pila original a 3121 cocos.

Otro método consiste en usar objetos adicionales para aclarar el proceso de división. Supongamos que por la noche agregamos cuatro cocos azules al montón. Entonces, el primer marinero que se despierte encontrará que el montón es divisible por cinco, en lugar de tener un coco sobrante. El marinero divide el montón en quintos de manera que cada coco azul esté en un quinto diferente; luego toma el quinto sin coco azul, le da uno de sus cocos al mono y vuelve a juntar los otros cuatro quintos (incluyendo los cuatro cocos azules). Cada marinero hace lo mismo. Durante la división final por la mañana, los cocos azules quedan a un lado, sin pertenecer a nadie. Dado que todo el montón se dividió equitativamente 5 veces durante la noche, debe haber contenido 5 × ⁵ cocos: 4 cocos azules y 3121 cocos comunes.

El recurso de utilizar objetos adicionales para ayudar a conceptualizar una división apareció ya en 1912 en una solución propuesta por Norman H. Anning . ^{[ 3 ] [ 16 ]}

Un ejemplo similar aparece en el acertijo de la herencia de 17 animales : Un hombre lega 17 caballos a sus tres hijos, especificando que el mayor recibe la mitad, el segundo un tercio y el menor un noveno. Los hijos, desconcertados, consultan a un astuto comerciante de caballos. Este les dice: «Tomen prestado mi caballo». Los hijos reparten los caballos y descubren que todas las divisiones resultan iguales, sobrando un caballo que devuelven al comerciante.

Una solución sencilla aparece cuando las divisiones y restas se realizan en base 5. Consideremos la resta, cuando el primer marinero toma su parte (y la del mono). Sean n₀ _, n₁ _, ... los dígitos de N, el número de cocos en la pila original, y s₀ _, s₁ _, ... los dígitos de la parte del marinero S, ambos en base 5. Después de la parte del mono, el dígito menos significativo de N debe ser 0; después de la resta, el dígito menos significativo de N' que queda del primer marinero debe ser 1, por lo tanto, lo siguiente (el número real de dígitos en N y S es desconocido, pero es irrelevante por ahora):

n 5 n 4 n 3 n 2 n 1 0 (N 5 ) s 4 s 3 s 2 s 1 s 0 (S 5 ) 1 (N' 5 )

El dígito que se resta de 0 en base 5 para obtener 1 es 4, por lo que s ₀ =4. Pero como S es (N-1)/5, y dividir por 5 _es simplemente desplazar el número una posición a la derecha, n ₁ =s ₀ =4. Entonces, ahora la resta se ve así:

n 5 n 4 n 3 n 2 4 0 s 4 s 3 s 2 s 1 4 1

Como el siguiente marinero va a hacer lo mismo en N', el dígito menos significativo de N' se convierte en 0 después de lanzar uno al mono, y el LSD de S' debe ser 4 por la misma razón; el siguiente dígito de N' también debe ser 4. Así que ahora se ve así:

n 5 n 4 n 3 n 2 4 0 s 4 s 3 s 2 s 1 4 4 1

Tomando prestado 1 de n ₁ (que ahora es 4) queda 3, por lo que s ₁ debe ser 4, y por lo tanto n ₂ también. Entonces ahora se ve así:

n 5 n 4 n 3 4 4 0 s 4 s 3 s 2 4 4 4 1

Pero el mismo razonamiento se aplica de nuevo a N' como se aplica a N, por lo que el siguiente dígito de N' es 4, por lo que s ₂ y n ₃ también son 4, etc. Hay 5 divisiones; las primeras cuatro deben dejar un número impar en base 5 en la pila para la siguiente división, pero la última división debe dejar un número par en base 5 para que la división de la mañana resulte par (en 5). Por lo tanto, hay cuatro 4 en N después de un LSD de 1: N=44441 ₅ =3121 ₁₀

Un análisis numérico sencillo sería el siguiente: Si N es el número inicial, cada uno de los 5 marineros realiza la transición de la pila original de la siguiente manera:

N => 4(N–1)/5 o equivalentemente, N => 4(N+4)/5 – 4.

Repitiendo esta transición 5 veces se obtiene el número restante por la mañana:

N => 4(N+4)/5 – 4

   => 16(N+4)/25 – 4

   => 64(N+4)/125 – 4

   => 256(N+4)/625 – 4

   => 1024(N+4)/3125 – 4

Dado que ese número debe ser un entero y 1024 es primo relativo con 3125, N+4 debe ser un múltiplo de 3125. El múltiplo más pequeño es 3125 · 1, por lo que N = 3125 – 4 = 3121; el número que queda por la mañana es 1020, que es divisible exactamente por 5, como se requiere. 

Se puede obtener una solución simple y concisa utilizando directamente la estructura recursiva del problema: Hubo cinco divisiones de los cocos en quintos, quedando uno sobrante en cada ocasión (dejando de lado la última división de la mañana). La pila que queda después de cada división debe contener un número entero de cocos. Si solo hubo una división de este tipo, entonces es evidente que 5 · 1+1=6 es una solución. De hecho, cualquier múltiplo de cinco más uno es una solución, por lo que una posible fórmula general es 5 · k – 4, ya que un múltiplo de 5 más 1 también es un múltiplo de 5 menos 4. Así que 11, 16, etc., también funcionan para una división. ^{[ 17 ]}  

Si se hacen dos divisiones, se debe usar un múltiplo de 5 · 5 = 25 en lugar de 5, porque 25 se puede dividir entre 5 dos veces. Entonces, el número de cocos que podría haber en el montón es k · 25 – 4. k = 1 da como resultado 21 es el número positivo más pequeño que se puede dividir sucesivamente entre 5 dos veces con resto 1. Si hay 5 divisiones, entonces se requieren múltiplos de 5 ⁵ = 3125; el número más pequeño de este tipo es 3125 – 4 = 3121. Después de 5 divisiones, quedan 1020 cocos, un número divisible por 5 como lo requiere el problema. De hecho, después de n divisiones, se puede demostrar que el montón restante es divisible por n , una propiedad que el creador del problema utilizó convenientemente.  

Una forma formal de expresar el argumento anterior es:

La pila original de cocos se dividirá entre 5 un total de 5 veces con un resto de 1, sin considerar la última división de la mañana. Sea N = número de cocos en la pila original. Cada división debe dejar el número de cocos en la misma clase de congruencia (mod 5). Entonces,

${\displaystyle N\equiv 4/5\cdot (N-1)}$(mod 5) (el –1 es la nuez lanzada al mono)

${\displaystyle 5N\equiv 4N-4}$(módulo 5)

${\displaystyle N\equiv -4}$(módulo 5) (–4 es la clase de congruencia)

Si comenzamos con la clase módulo -4, permaneceremos en la clase módulo -4. Dado que, en última instancia, debemos dividir el montón 5 veces, es decir, 5⁵, el montón original era de 5⁵ - 4 = 3121 cocos. El resto de 1020 cocos se divide fácilmente entre 5. Esta solución, en esencia, invierte la forma en que (probablemente) se planteó el problema.

La ecuación diofántica equivalente para esta versión es:

${\displaystyle 1024N=15625F+8404}$(1)

donde N es la cantidad original de cocos y F es la cantidad recibida por cada marinero en la última división de la mañana. Esta ecuación difiere mínimamente de la ecuación anterior para el problema predecesor, y su resolubilidad está garantizada por el mismo razonamiento.

Reordenar,

${\displaystyle 1024N-15625F=8404}$(2)

Esta ecuación diofántica tiene una solución que se deduce directamente del algoritmo euclidiano ; de hecho, tiene infinitas soluciones periódicas, tanto positivas como negativas. Si (x ₀ , y ₀ ) es una solución de 1024x–15625y=1, entonces N ₀ =x ₀ · 8404, F ₀ =y ₀ · 8404 es una solución de (2), lo que significa que cualquier solución debe tener la forma  

${\displaystyle {\begin{cases}N=N_{0}+15625\cdot t\\F=F_{0}+1024\cdot t\end{cases}}}$(3)

dónde${\displaystyle t}$es un parámetro arbitrario que puede tener cualquier valor entero.

Se pueden tomar ambos lados de (1) módulo 1024, por lo tanto

${\displaystyle 1024N=15625F+8404\mod 1024}$

Otra forma de pensarlo es que para que${\displaystyle n}$Para que sea un número entero, el lado derecho de la ecuación debe ser un múltiplo entero de 1024; esa propiedad no se verá alterada al factorizar tantos múltiplos de 1024 como sea posible del lado derecho. Reduciendo ambos lados por múltiplos de 1024,

${\displaystyle 0=(15625F-15\cdot 1024F)+(8404-8\cdot 1024)\mod 1024}$

restando,

${\displaystyle 0=265F+212\mod 1024}$

factorización,

${\displaystyle 0=53\cdot (5F+4)\mod 1024}$

El lado derecho debe seguir siendo un múltiplo de 1024; dado que 53 es primo relativo a 1024, 5F + 4 debe ser un múltiplo de 1024. El múltiplo más pequeño es 1 · 1024, por lo que 5F + 4 = 1024 y F = 204. Sustituyendo en (1) 

${\displaystyle 1024N=15625\cdot 204+8404\Rightarrow N={\frac {3195904}{1024}}\Rightarrow N=3121}$

El algoritmo euclidiano es bastante tedioso, pero es una metodología general para resolver ecuaciones racionales ax+by=c que requieren respuestas enteras. De (2) anterior, es evidente que 1024 (2 ¹⁰ ) y 15625 (5 ⁶ ) son primos relativos y, por lo tanto, su MCD es 1, pero necesitamos las ecuaciones de reducción para la sustitución hacia atrás para obtener N y F en términos de estas dos cantidades:

Primero, obtén restos sucesivos hasta que quede el MCD:

15625 = 15·1024 + 265 (a)

1024 = 3·265 + 229 (b)

265 = 1·229 + 36 (c)

229 = 6·36 + 13 (d)

36 = 2·13 + 10 (e)

13 = 1·10 + 3 (f)

10 = 3·3 + 1 (g) (el resto 1 es el máximo común divisor de 15625 y 1024)

1 = 10 – 3(13–1·10) = 4·10 – 3·13 (reordenar (g), sustituir 3 de (f) y combinar)

1 = 4·(36 – 2·13) – 3·13 = 4·36 – 11·13 (sustituir 10 de (e) y combinar)

1 = 4·36 – 11·(229 – 6·36) = –11·229 + 70*36 (sustituir 13 de (d) y combinar)

1 = –11·229 + 70·(265 – 1·229) = –81·229 + 70·265 (sustituir 36 de (c) y combinar)

1 = –81·(1024 – 3·265) + 70·265 = –81·1024 + 313·265 (sustituir 229 de (b) y combinar)

1 = –81·1024 + 313·(15625 – 15·1024) = 313·15625 – 4776·1024 (sustituir 265 de (a) y combinar)

Entonces el par (N ₀ ,F ₀ ) = (-4776·8404, -313*8404); el más pequeño${\displaystyle t}$(véase (3) en la subsección anterior) que hará que tanto N como F sean positivos es 2569, por lo tanto:

${\displaystyle N=N_{0}+15625\cdot 2569=3121}$

${\displaystyle F=F_{0}+1024\cdot 2569=204}$

Alternativamente, se puede usar una fracción continua, cuya construcción se basa en el algoritmo euclidiano. La fracción continua para 1024 ⁄ 15625 (0.065536 exactamente) es [;15,3,1,6,2,1, 3 ]; ^{[ 18 ]} su convergente terminada después del período es 313 ⁄ 4776 , lo que nos da x ₀ =–4776 e y ₀ =313. El menor valor de t para el cual tanto N como F son no negativos es 2569, por lo que

${\displaystyle N=-4776\cdot 8404+15625\cdot 2569=3121}$.

Este es el número positivo más pequeño que satisface las condiciones del problema.

Cuando el número de marineros es un parámetro, sea${\displaystyle m}$En lugar de un valor computacional, una cuidadosa reducción algebraica de la relación entre el número de cocos en la pila original y el número asignado a cada marinero por la mañana produce una relación diofántica análoga cuyos coeficientes son expresiones en${\displaystyle m}$.

El primer paso es obtener una expansión algebraica de la relación de recurrencia correspondiente a la transformación de cada marinero del montón,${\displaystyle n_{i}}$siendo el número dejado por el marinero:

${\displaystyle n_{i}={\frac {m-1}{m}}(n_{i-1}-1)}$

dónde${\displaystyle n_{i\rightarrow 0}\equiv N}$, el número reunido originalmente, y${\displaystyle n_{i\rightarrow m}}$el número que queda por la mañana. Ampliando la recurrencia mediante sustitución${\displaystyle n_{i}}$para${\displaystyle n_{i-1}}$${\displaystyle m}$veces produce:

${\displaystyle n_{m}=\left({\frac {m-1}{m}}\right)^{m}\cdot n_{0}-\left[({\frac {m-1}{m}})^{m}+...+({\frac {m-1}{m}})^{2}+{\frac {m-1}{m}}\right]}$

Factorizando el último término,

${\displaystyle n_{m}=\left({\frac {m-1}{m}}\right)^{m}\cdot n_{0}-\left({\frac {m-1}{m}}\right)\cdot \left[({\frac {m-1}{m}})^{m-1}+...+{\frac {m-1}{m}}+1\right]}$

El polinomio en serie de potencias entre corchetes de la forma${\displaystyle x^{m-1}+...+x+1}$suma a${\displaystyle (1-x^{m})/(1-x)}$entonces,

${\displaystyle n_{m}=\left({\frac {m-1}{m}}\right)^{m}\cdot n_{0}-\left({\frac {m-1}{m}}\right)\cdot \left[\left(1-({\frac {m-1}{m}})^{m}\right){\bigg /}\left(1-({\frac {m-1}{m}})\right)\right]}$

lo cual se simplifica a:

${\displaystyle n_{m}=\left({\frac {m-1}{m}}\right)^{m}\cdot n_{0}-(m-1)\cdot {\frac {m^{m}-(m-1)^{m}}{m^{m}}}}$

Pero${\displaystyle n_{m}}$es el número que queda por la mañana que es un múltiplo de${\displaystyle m}$(es decir${\displaystyle F}$(el número asignado a cada marinero por la mañana):

${\displaystyle m\cdot F=\left({\frac {m-1}{m}}\right)^{m}\cdot n_{0}-(m-1)\cdot {\frac {m^{m}-(m-1)^{m}}{m^{m}}}}$

Resolver para${\displaystyle n_{0}}$(=${\displaystyle N}$),

${\displaystyle N=m^{m}\cdot {\frac {m-1+m\cdot F}{(m-1)^{m}}}-(m-1)}$

La ecuación es una ecuación diofántica lineal en dos variables,${\displaystyle N}$y${\displaystyle F}$.${\displaystyle m}$es un parámetro que puede ser cualquier número entero. La naturaleza de la ecuación y el método de su solución no dependen de${\displaystyle m}$.

Ahora se aplican consideraciones de teoría de números. Para${\displaystyle N}$Para ser un número entero, es suficiente que${\displaystyle {\frac {m-1+m\cdot F}{(m-1)^{m}}}}$sea ​​un número entero, así que sea${\displaystyle r}$:

${\displaystyle r={\frac {m-1+m\cdot F}{(m-1)^{m}}}}$

La ecuación debe transformarse en la forma${\displaystyle ax+by=\pm 1}$cuyas soluciones son formuladas. Por lo tanto:

${\displaystyle (m-1)^{m}\cdot r-m\cdot s=-1}$, dónde${\displaystyle s=1+F}$

Porque${\displaystyle m}$y${\displaystyle m-1}$son primos relativos, existen soluciones enteras${\displaystyle (r,s)}$por la identidad de Bézout. Esta ecuación se puede reformular como:

${\displaystyle (m-1)^{m}\cdot r\equiv -1\mod m}$

Pero ( m –1) ^{m es} _un polinomio Z · m –1 si m es impar y Z · m +1 si m es par, donde Z es un polinomio con base monomial en m . Por lo tanto, _r0 = 1 si m es impar y r0 = –1 si m es par es una solución.  

La identidad de Bézout proporciona la solución periódica.${\displaystyle r=r_{0}+k\cdot m}$, por lo que sustituye por${\displaystyle r}$en la ecuación diofántica y reordenando:

${\displaystyle N=r_{0}\cdot m^{m}-(m-1)+k\cdot m^{m+1}}$

dónde${\displaystyle r_{0}=1}$para${\displaystyle m}$extraño y${\displaystyle r_{0}=-1}$para${\displaystyle m}$incluso y${\displaystyle k}$es cualquier número entero. ^{[ 19 ]} Para un dado${\displaystyle m}$, el más pequeño positivo${\displaystyle k}$será elegido de tal manera que${\displaystyle N}$Satisface las restricciones del enunciado del problema.

En la versión del problema de William,${\displaystyle m}$son 5 marineros, así que${\displaystyle r_{0}}$es 1, y${\displaystyle k}$Se puede tomar como cero para obtener la respuesta positiva más baja, por lo que N = 1 · 5 ⁵ – 4 = 3121 para el número de cocos en la pila original. (Cabe señalar que la siguiente solución secuencial de la ecuación para k = –1 es –12504, por lo que el método de prueba y error alrededor de cero no resolverá la versión de Williams del problema, a diferencia de la versión original cuya ecuación, fortuitamente, tenía una solución negativa de pequeña magnitud). 

Aquí hay una tabla de las soluciones positivas.${\displaystyle N}$para los primeros${\displaystyle m}$(${\displaystyle k}$es cualquier número entero no negativo):

Otras variantes, incluido el supuesto problema del predecesor, tienen soluciones generales relacionadas para un número arbitrario de marineros.

Cuando la división matutina también tiene un resto de uno, la solución es:

${\displaystyle N=-(m-1)+k\cdot m^{m+1}}$

Para${\displaystyle m=5}$y${\displaystyle k=1}$Esto da como resultado 15.621 como el número positivo más pequeño de cocos para la versión del problema anterior a William.

En algunas formas alternativas anteriores del problema, las divisiones resultaban iguales y las nueces (u otros elementos) se asignaban del montón restante después de la división. En estas formas, la relación de recursión es:

${\displaystyle n_{i}={\frac {m-1}{m}}n_{i-1}-1}$

La forma alternativa también tenía dos finales: cuando la división matutina resulta par y cuando queda una nuez para el mono. Cuando la división matutina resulta par, la solución general se reduce mediante una derivación similar a:

${\displaystyle N=-m+k\cdot m^{m+1}}$

Por ejemplo, cuando${\displaystyle m=4}$y${\displaystyle k=1}$La pila original tiene 1020 cocos, y después de cuatro divisiones iguales sucesivas durante la noche, asignando un coco al mono después de cada división, quedan 80 cocos por la mañana, por lo que la división final resulta en un resultado equilibrado sin que sobre ningún coco.

Cuando al dividir por la mañana queda una nuez, la solución general es:

${\displaystyle N=r_{0}\cdot m^{m}-m+k\cdot m^{m+1}}$

dónde${\displaystyle r_{0}=-1}$si${\displaystyle m}$es extraño, y${\displaystyle r_{0}=1}$si${\displaystyle m}$es par. Por ejemplo, cuando${\displaystyle m=3}$,${\displaystyle r_{0}=-1}$y${\displaystyle k=1}$La pila original tiene 51 cocos, y después de tres divisiones sucesivas durante la noche, asignándose un coco al mono después de cada división, quedan 13 cocos por la mañana, por lo que en la división final queda un coco para el mono.

En la literatura se han tratado otras variantes posteriores a Williams que especifican diferentes restos, incluidos los positivos (es decir, el mono añade cocos al montón). La solución es:

${\displaystyle N=r_{0}\cdot m^{m}-c\cdot (m-1)+k\cdot m^{m+1}}$

dónde${\displaystyle r_{0}=1}$para${\displaystyle m}$extraño y${\displaystyle r_{0}=-1}$para${\displaystyle m}$incluso,${\displaystyle c}$es el resto después de cada división (o número de monos) y${\displaystyle k}$es cualquier número entero (${\displaystyle c}$es negativo si los monos añaden cocos al montón).

Otras variantes, en las que el número de hombres o los restos varían entre divisiones, generalmente quedan fuera de la clase de problemas asociados con el mono y los cocos, aunque también se reducen a ecuaciones diofánticas lineales con dos variables. Sus soluciones se obtienen mediante las mismas técnicas y no presentan nuevas dificultades.