El mono y los cocos

Rompecabezas matemático

El mono y los cocos es un acertijo matemático en el campo del análisis diofántico que se originó a partir de un cuento que involucra a cinco marineros y un mono en una isla desierta que se dividen una pila de cocos ; el problema es encontrar la cantidad de cocos en la pila original (no se permiten cocos fraccionarios). El problema es conocido por su desconcertante dificultad para los solucionadores de acertijos no sofisticados, aunque con el enfoque matemático adecuado, la solución es trivial. El problema se ha convertido en un elemento básico en las colecciones de matemáticas recreativas .

Descripción general

El problema se puede expresar como:

Hay un montón de cocos, propiedad de cinco hombres. Un hombre divide el montón en cinco montones iguales, le da el coco que queda a un mono que pasa y se lleva su propia parte. El segundo hombre repite el procedimiento, divide el montón restante en cinco y se lleva su parte, al igual que el tercero, el cuarto y el quinto, cada uno de ellos encuentra un coco que queda al dividir el montón por cinco y se lo da a un mono. Finalmente, el grupo divide los cocos restantes en cinco montones iguales: esta vez no queda ningún coco.

¿Cuántos cocos había en la pila original?

El problema del mono y los cocos es el representante más conocido de una clase de problemas de lógica que requieren soluciones enteras estructuradas como división recursiva o fraccionamiento de alguna cantidad discretamente divisible, con o sin residuos, y una división final en una cierta cantidad de partes iguales, posiblemente con un residuo. El problema es tan conocido que a toda la clase se la suele denominar en términos generales "problemas del tipo del mono y el coco", aunque la mayoría no están estrechamente relacionados con el problema.

Otro ejemplo: “Tengo un número entero de libras de cemento, no sé cuántas, pero después de añadir una novena y una undécima parte, se repartió en 3 sacos, cada uno con un número entero de libras. ¿Cuántas libras de cemento tenía?”

Los problemas piden la cantidad inicial o terminal. Se indica o implica el número positivo más pequeño que podría ser una solución. Hay dos incógnitas en estos problemas, el número inicial y el número terminal, pero solo una ecuación que es una reducción algebraica de una expresión para la relación entre ellos. La clase tiene en común la naturaleza de la ecuación resultante, que es una ecuación diofántica lineal con dos incógnitas. La mayoría de los miembros de la clase son determinados, pero algunos no lo son (el mono y los cocos es uno de estos últimos). Los métodos algebraicos familiares no sirven para resolver estas ecuaciones.

Historia

El origen de la clase de tales problemas se ha atribuido al matemático indio Mahāvīra en el capítulo VI, § 131 1 ⁄ 2 , 132 1 ⁄ 2 de su Ganita-sara-sangraha ("Compendio de la esencia de las matemáticas"), alrededor del 850 d. C., que trataba de la división en serie de frutas y flores con residuos específicos. ^[1] Eso haría que los problemas progenitores tuvieran más de 1000 años de antigüedad antes de su resurgimiento en la era moderna. Los problemas que involucran división que invocan el teorema chino del residuo aparecieron en la literatura china ya en el siglo I d. C. Sun Tzu preguntó: Encuentra un número que deje los residuos 2, 3 y 2 cuando se divide por 3, 5 y 7, respectivamente. Diofanto de Alejandría estudió por primera vez los problemas que requerían soluciones enteras en el siglo III d. C. El algoritmo euclidiano del máximo común divisor que sustenta la solución de tales problemas fue descubierto por el geómetra griego Euclides y publicado en sus Elementos en el año 300 a. C.

El profesor David Singmaster , un historiador de los rompecabezas, rastrea una serie de problemas menos plausibles relacionados a lo largo de la Edad Media, con algunas referencias que se remontan al imperio babilónico alrededor de 1700 a. C. Involucran el tema general de sumar o restar fracciones de una pila o números específicos de objetos discretos y preguntarse cuántos podría haber habido al principio. La siguiente referencia a un problema similar se encuentra en Récréations mathématiques et physiques de Jacques Ozanam , 1725. En el ámbito de las matemáticas puras, Lagrange en 1770 expuso su teorema de fracción continua y lo aplicó a la solución de ecuaciones diofánticas.

La primera descripción del problema en su forma moderna aparece en los diarios de Lewis Carroll en 1888: consiste en dividir en serie una pila de nueces sobre una mesa entre cuatro hermanos, cada vez con el resto de una unidad entregada a un mono, y la división final resulta igual. El problema nunca apareció en ninguna de las obras publicadas de Carroll, aunque a partir de otras referencias ^{[¿ cuáles? ]} parece que el problema estaba en circulación en 1888. Un problema casi idéntico apareció en Elementary Algebra (Álgebra elemental ) de WW Rouse Ball (1890). ^{[ cita requerida ]} El problema se mencionaba en obras de matemáticos de la época, con soluciones, en su mayoría erróneas, lo que indica que el problema era nuevo y desconocido en ese momento. ^{[ cita requerida ]}

El problema se hizo notorio cuando el novelista y cuentista estadounidense Ben Ames Williams modificó un problema más antiguo y lo incluyó en una historia, "Coconuts", en la edición del 9 de octubre de 1926 del Saturday Evening Post . ^[2] Así es como Williams planteó el problema ^[3] (condensado y parafraseado):

Cinco hombres y un mono naufragaron en una isla. Pasaron el primer día recolectando cocos para alimentarse.

Por la noche, un hombre se despertó y decidió tomar su parte temprano. Así que dividió los cocos en cinco montones. Le sobró un coco y se lo dio al mono. Luego escondió su montón y volvió a juntar el resto.

Poco a poco, los cinco hombres se despertaron y, uno tras otro, hicieron lo mismo: cada uno tomó la quinta parte de los cocos que había en el montón cuando se despertó y dejó uno para el mono. Por la mañana se dividieron los cocos que quedaban y les tocó en cinco partes iguales. Por supuesto, cada uno debía saber que faltaban cocos, pero cada uno era culpable como los demás, así que no dijeron nada.

¿Cuántos cocos había en la pila original?

Williams no había incluido una respuesta en la historia. La revista se vio inundada por más de 2.000 cartas pidiendo una solución al problema. El editor del Post , Horace Lorimer , envió un famoso telegrama a Williams diciendo: "POR EL AMOR DE MIKE, ¿CUÁNTOS COCOS HAY? EL INFIERNO ESTALLANDO POR AQUÍ". Williams siguió recibiendo cartas pidiendo una solución o proponiendo nuevas durante los siguientes veinte años. ^[3]

Martin Gardner presentó el problema en su columna Mathematical Games de abril de 1958 en Scientific American . Según Gardner, Williams había modificado un problema más antiguo para hacerlo más confuso. En la versión anterior hay un coco para el mono en la división final; en la versión de Williams, la división final de la mañana sale igualada. Pero la evidencia histórica disponible no indica a qué versiones tuvo acceso Williams. ^[4] Gardner le dijo una vez a su hijo Jim que era su problema favorito. ^[5] Dijo que el Mono y los Cocos es "probablemente el rompecabezas diofántico más trabajado y menos resuelto". ^[2] Desde entonces, la versión de Williams del problema se ha convertido en un elemento básico de las matemáticas recreativas . ^[6] La historia original que contiene el problema fue reimpresa íntegramente en la antología de Clifton Fadiman de 1962 The Mathematical Magpie , ^[7] un libro que la Asociación Matemática de Estados Unidos recomienda para su adquisición por parte de las bibliotecas de matemáticas de pregrado. ^[8]

En la literatura han aparecido numerosas variantes que varían el número de marineros, monos o cocos. ^[9]

Soluciones

Un problema diofántico

El análisis diofántico es el estudio de ecuaciones con coeficientes racionales que requieren soluciones enteras. En los problemas diofánticos, hay menos ecuaciones que incógnitas. La información "extra" necesaria para resolver las ecuaciones es la condición de que las soluciones sean números enteros. Cualquier solución debe satisfacer todas las ecuaciones. Algunas ecuaciones diofánticas no tienen solución, algunas tienen una o un número finito, y otras tienen infinitas soluciones.

El mono y los cocos se reduce a una ecuación diofántica lineal de dos variables de la forma

ax + by = c , o más generalmente,

(a/d)x + (b/d)y = c/d

donde d es el máximo común divisor de a y b . ^[10] Por la identidad de Bézout , la ecuación es solucionable si y solo si d divide a c . Si es así, la ecuación tiene infinitas soluciones periódicas de la forma

x = x ₀ + t  · b ,

y = y ₀ + t  · a

donde ( x ₀ , y ₀ ) es una solución y t es un parámetro que puede ser cualquier entero. El problema no está pensado para ser resuelto por ensayo y error; existen métodos deterministas para resolver ( x ₀ , y ₀ ) en este caso (ver texto).

Se han publicado numerosas soluciones desde 1928 tanto para el problema original como para la modificación de Williams. ^{[11] [12] [13] [14]}

Antes de entrar en la solución del problema, se pueden señalar un par de cosas. Si no hubiera restos, dado que hay 6 divisiones de 5, 5 ⁶ = 15.625 cocos deben estar en la pila; en la sexta y última división, cada marinero recibe 1024 cocos. Ningún número positivo menor dará como resultado que las 6 divisiones salgan iguales. Eso significa que en el problema tal como se plantea, cualquier múltiplo de 15.625 puede agregarse a la pila, y satisfará las condiciones del problema. Eso también significa que el número de cocos en la pila original es menor que 15.625, de lo contrario, restar 15.625 dará como resultado una solución menor. Pero el número en la pila original no es trivialmente pequeño, como 5 o 10 (por eso este es un problema difícil): puede ser del orden de cientos o miles. A diferencia del ensayo y error en el caso de adivinar una raíz polinómica, el ensayo y error para una raíz diofántica no dará como resultado ninguna convergencia obvia. No existe una forma sencilla de estimar cuál será la solución.

La versión original

Versión original, con un coco sobrante

La columna Mathematical Games de Martin Gardner de 1958 comienza su análisis resolviendo el problema original (con un coco restante también en la mañana) porque es más fácil que la versión de Williams. Sea F el número de cocos recibidos por cada marinero después de la división final en 5 partes iguales en la mañana. Entonces, el número de cocos que quedan antes de la división de la mañana es ; el número presente cuando el quinto marinero se despertó fue ; el número presente cuando el cuarto marinero se despertó fue ; y así sucesivamente. Encontramos que el tamaño N de la pila original satisface la ecuación diofántica ^[3] ${\displaystyle 5F+1}$ ${\displaystyle {\tfrac {5}{4}}(5F+1)+1={\tfrac {25}{4}}F+{\tfrac {9}{4}}}$ ${\displaystyle {\tfrac {5}{4}}({\tfrac {25}{4}}F+{\tfrac {9}{4}})+1={\tfrac {125}{16}}F+{\tfrac {241}{16}}}$

${\displaystyle 1024N=15625F+11529}$

Gardner señala que esta ecuación es "demasiado difícil de resolver por ensayo y error", ^[3] pero presenta una solución que atribuye a JHC Whitehead (a través de Paul Dirac ): ^[3] La ecuación también tiene soluciones en números enteros negativos. Probando algunos números negativos pequeños resulta que es una solución. ^[15] Sumamos 15625 a N y 1024 a F para obtener la solución positiva más pequeña: . ${\displaystyle N=-4,F=-1}$ ${\displaystyle N=15621,F=1023}$

Versión de Williams

La versión de Williams, sin cocos sobrantes

El método de prueba y error no logra resolver la versión de Williams, por lo que se necesita un enfoque más sistemático.

Usando un colador

El espacio de búsqueda se puede reducir mediante una serie de factores cada vez mayores observando la estructura del problema, de modo que con un poco de ensayo y error se encuentre la solución. El espacio de búsqueda es mucho más pequeño si se comienza con el número de cocos que recibió cada hombre en la división de la mañana, porque ese número es mucho menor que el número que había en la pila original.

Si F es el número de cocos que cada marinero recibe en la división final en la mañana, la pila en 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. Entonces, la pila de la mañana, llamada el 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, por lo que la pila de la mañana debe ser algún múltiplo de 20 que produzca una pila divisible por 4 antes de que el último marinero se despierte. Sucede que 3*20=60 funciona para dos marineros: aplicar la fórmula de recursión para n dos veces produce 96 como el número más pequeño de cocos en la pila original. 96 es divisible por 4 una vez más, por lo que para 3 marineros que se despiertan, la pila podría haber sido 121 cocos. Pero 121 no es divisible por 4, por lo que para 4 marineros que se despiertan, uno necesita hacer otro salto. En este punto, la analogía se vuelve obtusa, porque para dar cabida a 4 marineros que se despiertan, la pila de la mañana debe ser algún múltiplo de 60: si uno es persistente, se puede descubrir que 17*60=1020 hace el truco y el número mínimo en la pila original sería 2496. Una última iteración en 2496 para 5 marineros que se despiertan, es decir 5/4(2496)+1 lleva la pila original a 3121 cocos.

Cocos azules

Otro recurso consiste en utilizar objetos adicionales para aclarar el proceso de división. Supongamos que por la noche añadimos cuatro cocos azules a la pila. Entonces, el primer marinero que se despierte encontrará que la pila es divisible por cinco, en lugar de que le sobre un coco. El marinero divide la pila en quintos de modo que cada coco azul esté en un quinto diferente; luego toma el quinto que no tiene coco azul, le da uno de sus cocos al mono y vuelve a juntar los otros cuatro quintos (incluidos los cuatro cocos azules). Cada marinero hace lo mismo. Durante la división final de la mañana, los cocos azules quedan a un lado, sin pertenecer a nadie. Como toda la pila se dividió de manera uniforme 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 de Norman H. Anning . ^{[3] [16]}

Un mecanismo similar aparece en el rompecabezas de la herencia de los 17 animales : un hombre deja en herencia 17 caballos a sus tres hijos, especificando que el hijo mayor recibe la mitad, el hijo siguiente un tercio y el hijo menor, una novena parte de los animales. Los hijos están confundidos, por lo que consultan a un sabio comerciante de caballos. Este les dice: "Toma, toma prestado mi caballo". Los hijos dividen debidamente los caballos, y descubren que todas las divisiones salen iguales, con un caballo restante, que devuelven al comerciante.

Numeración de base 5

Una solución sencilla aparece cuando las divisiones y las restas se realizan en base 5. Consideremos la resta, cuando el primer marinero toma su parte (y la del mono). Sea 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 ahora 0; después de la resta, el dígito menos significativo de N' dejado por el primer marinero debe ser 1, de ahí lo siguiente (el número real de dígitos en N así como en S es desconocido, pero son irrelevantes por ahora):

n 5 n 4 n 3 n 2 n 1 0 (N 5 ) s4s3s2s1s0 ( S5 )​​​​​​​​​ 1 (Número 5 )

El dígito restado de 0 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 hacia la derecha, n ₁ = s ₀ = 4. Así que ahora la resta se ve así:

n5n4n3n240​​​​​​​​ y 4 y 3 y 2 y 1 y 4 1

Como el próximo 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í:

n5n4n3n240​​​​​​​​ y 4 y 3 y 2 y 1 y 4 4 1

Si tomamos prestado 1 de n ₁ (que ahora es 4), obtenemos 3, por lo que s ₁ debe ser 4 y, por lo tanto, n ₂ también. Así que ahora queda así:

n.º 5 n.º 4 n.º 3 4 4 0 y 4 y 3 y 2 y 4 4 1

Pero el mismo razonamiento se aplica a N' como se aplicó 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 de base 5 en la pila para la siguiente división, pero la última división debe dejar un número par de base 5 para que la división de la mañana salga par (en 5). Por lo tanto, hay cuatro 4 en N después de un LSD de 1: N = 44441 ₅ = 3121 ₁₀

Un enfoque numérico

Un análisis numérico sencillo es el siguiente: si N es el número inicial, cada uno de los 5 marineros hace la transición a 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 obtenemos el número que queda 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

Como ese número debe ser un entero y 1024 es primo relativo de 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 por 5 como se requiere.

Congruencia de módulo

Se puede obtener una solución simple y concisa utilizando directamente la estructura recursiva del problema: hubo cinco divisiones de los cocos en quintos, y cada vez sobró uno (dejando de lado la división final 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 ese 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. Por lo tanto, 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 por 5 dos veces. Entonces, el número de cocos que podría haber en la pila es k  · 25 – 4. k = 1, lo que da 21, es el número positivo más pequeño que se puede dividir sucesivamente por 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 estos 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 la pila restante es divisible por n , una propiedad que el creador del problema utilizó convenientemente.

Una forma formal de enunciar el argumento anterior es:

La pila original de cocos se dividirá por 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 la cantidad de nueces en la misma clase de congruencia (mód 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}$(mod 5) (–4 es la clase de congruencia)

Por lo tanto, si comenzamos en la clase módulo -4 nueces, permaneceremos en la clase módulo -4. Como en última instancia tenemos que dividir la pila 5 veces o 5^5, la pila original era 5^5 – 4 = 3121 cocos. El resto de 1020 cocos se divide convenientemente de manera uniforme por 5 en la mañana. Esta solución esencialmente invierte la forma en que (probablemente) se construyó el problema.

La ecuación diofántica y formas de solución

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

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

donde N es el número original de cocos y F es el número que recibió cada marinero en la división final de la mañana. Esto es sólo trivialmente diferente de la ecuación anterior para el problema anterior, y la solución está garantizada por el mismo razonamiento.

Reordenando,

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

Esta ecuación diofántica tiene una solución que se desprende directamente del algoritmo euclidiano ; de hecho, tiene infinitas soluciones periódicas positivas y 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)

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

Un enfoque reduccionista

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

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

Otra forma de pensarlo es que 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 modificará si se factorizan tantos múltiplos de 1024 como sea posible del lado derecho. Al reducir ambos lados por múltiplos de 1024, ${\displaystyle n}$

${\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 RHS debe ser un múltiplo de 1024; dado que 53 es un primo relativo a 1024, 5 F + 4 debe ser un múltiplo de 1024. El múltiplo más pequeño es 1  · 1024, por lo que 5 F + 4 = 1024 y F = 204. Sustituyendo en (1)

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

Algoritmo euclidiano

El algoritmo euclidiano es bastante tedioso, pero es una metodología general para resolver ecuaciones racionales ax+by=c que requieren respuestas integrales. A partir de (2) anterior, es evidente que 1024 (2 ¹⁰ ) y 15625 (5 ⁶ ) son primos entre sí 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, obtenga los residuos sucesivos hasta que quede 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 MCD 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 en (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)

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

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

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

Fracción continua

Alternativamente, se puede utilizar 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 de la repetición es 313 ⁄ 4776 , lo que nos da x ₀ =–4776 e y ₀ =313. El valor mínimo de t para el que 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.

Una solución generalizada

Cuando el número de marineros es un parámetro, sea , en lugar de un valor computacional, una reducción algebraica cuidadosa 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}$ ${\displaystyle m}$

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

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

donde , el número de personas que se reunieron originalmente y el número que se fue por la mañana. Al expandir la recurrencia sustituyendo por veces, se obtiene: ${\displaystyle n_{i\rightarrow 0}\equiv N}$ ${\displaystyle n_{i\rightarrow m}}$ ${\displaystyle n_{i}}$ ${\displaystyle n_{i-1}}$ ${\displaystyle m}$

${\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]}$

La serie polinómica de potencias entre paréntesis de la forma suma así: ${\displaystyle x^{m-1}+...+x+1}$ ${\displaystyle (1-x^{m})/(1-x)}$

${\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, ¿el número que queda por la mañana es un múltiplo de (es decir , el número asignado a cada marinero por la mañana)? ${\displaystyle n_{m}}$ ${\displaystyle m}$ ${\displaystyle F}$

${\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}}}}$

Resolviendo 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 con dos variables, y . 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 N}$ ${\displaystyle F}$ ${\displaystyle m}$ ${\displaystyle m}$

Ahora se aplican las consideraciones de teoría de números. Para que sea un número entero, basta con que sea un número entero, por lo que sea : ${\displaystyle N}$ ${\displaystyle {\frac {m-1+m\cdot F}{(m-1)^{m}}}}$ ${\displaystyle r}$

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

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

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

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

${\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 r ₀ =1 si m es impar y r ₀ =–1 si m es par es una solución.

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

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

donde para impar y para par y es cualquier entero. ^[19] Para un dado , se elegirá el positivo más pequeño tal que satisfaga las restricciones del enunciado del problema. ${\displaystyle r_{0}=1}$ ${\displaystyle m}$ ${\displaystyle r_{0}=-1}$ ${\displaystyle m}$ ${\displaystyle k}$ ${\displaystyle m}$ ${\displaystyle k}$ ${\displaystyle N}$

En la versión de William del problema, hay 5 marineros, por lo tanto, es 1, y puede tomarse 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 ensayo 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). ${\displaystyle m}$ ${\displaystyle r_{0}}$ ${\displaystyle k}$

A continuación se muestra una tabla de las soluciones positivas para los primeros ( es cualquier número entero no negativo): ${\displaystyle N}$ ${\displaystyle m}$ ${\displaystyle k}$

Otras variantes y soluciones generales

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 resto uno, la solución es:

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

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

En algunas formas alternativas anteriores del problema, las divisiones resultaban iguales y las nueces (o elementos) se asignaban de la pila 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 daba un resultado par y cuando sobraba una nuez para el mono. Cuando la división matutina daba un resultado par, la solución general se reducía mediante una derivación similar a:

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

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

Cuando la división de la mañana da como resultado una nuez sobrante, la solución general es:

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

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

En la literatura se han estudiado otras variantes posteriores a Williams que especifican distintos residuos, incluidos los positivos (por ejemplo, el mono añade cocos a la pila). La solución es:

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

donde para impar y para par, es el resto después de cada división (o número de monos) y es cualquier número entero ( es negativo si los monos agregan cocos a la pila). ${\displaystyle r_{0}=1}$ ${\displaystyle m}$ ${\displaystyle r_{0}=-1}$ ${\displaystyle m}$ ${\displaystyle c}$ ${\displaystyle k}$ ${\displaystyle c}$

Otras variantes en las que el número de hombres o los residuos varían entre divisiones, por lo general 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 resuelven con las mismas técnicas y no presentan nuevas dificultades.

Véase también

• El problema del ganado de Arquímedes , un problema diofántico sustancialmente más difícil
• El último teorema de Fermat , posiblemente la ecuación diofántica más famosa de todas
• Problema de bala de cañón

Referencias

1. Cronología de las matemáticas recreativas de David Singmaster
2. Pleacher (2005)
3. Martin Gardner (2001). El libro colosal de las matemáticas. WW Norton & Company. págs. 3–9. ISBN 0-393-02023-1.
4. Antonic (2013)
5. Antonick (2013): "Luego le pregunté a Jim si su padre tenía un rompecabezas favorito, y él respondió casi de inmediato: 'Los monos [ sic ] y los cocos. Le encantaba ese'".
6. Wolfram Mathworld
7. RESEÑA DE KIRKUS de La Urraca Matemática 27 de julio de 1962
8. La urraca matemática, de Clifton Fadiman, Asociación Matemática de América, Springer, 1997
9. Pappas, T. "El mono y los cocos". El placer de las matemáticas. San Carlos, CA: Wide World Publ./Tetra, págs. 226-227 y 234, 1989.
10. d se puede encontrar si es necesario a través del algoritmo de Euclides
11. Underwood, RS y Robert E. Moritz. "3242". The American Mathematical Monthly 35, núm. 1 (1928): 47-48. doi:10.2307/2298601.
12. Kirchner, Roger B. "El problema generalizado del coco", The American Mathematical Monthly 67, no. 6 (1960): 516-19. doi:10.2307/2309167.
13. S. Singh y D. Bhattacharya, “Sobre la división de cocos: un problema diofántico lineal”, The College Mathematics Journal, mayo de 1997, págs. 203-4
14. G. Salvatore y T. Shima, "De cocos e integridad", Crux Mathematicorum, 4 (1978) 182–185
15. Bogomolny (1996)
16. Norman H. Anning (junio de 1912). "Departamento de problemas (#288)". Ciencias y matemáticas escolares . 12 (6).
17. Un caso especial es cuando k = 0, por lo que la pila inicial contiene -4 cocos. Esto funciona porque después de lanzar un coco positivo al mono, hay -5 cocos en la pila. Después de la división, quedan -4 cocos. No importa cuántas divisiones de este tipo se realicen, la pila restante contendrá -4 cocos. Esta es una anomalía matemática llamada "punto fijo". Solo unos pocos problemas tienen un punto así, pero cuando lo hay, hace que el problema sea mucho más fácil de resolver. Todas las soluciones del problema son múltiplos de 5 sumados o restados del punto fijo.
18. Ver aquí una exposición del método.
19. Gardner da una formulación equivalente pero bastante críptica al elegir inexplicablemente el no canónico cuando es par, y luego refactoriza la expresión de una manera que oculta la periodicidad: ${\displaystyle r_{0}=-1+1\cdot m}$ ${\displaystyle m}$

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

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

    donde es un parámetro que puede ser cualquier entero. ${\displaystyle k}$
20. Mientras que N = 3 satisface la ecuación, 11 es el número positivo más pequeño que le da a cada marinero un número positivo distinto de cero de cocos en cada división, una condición implícita del problema.

Fuentes

• Antonick, Gary (2013). El mono y los cocos de Martin Gardner en Numberplay The New York Times :, 7 de octubre de 2013
• Pleacher, David (2005). Problema de la semana: El mono y los cocos 16 de mayo de 2005
• Pappas, Theoni (1993). El placer de las matemáticas: descubrimiento de las matemáticas en todo el mundo, 23 de enero de 1993, ISBN 0933174659 
• Wolfram Mathworld: El problema del mono y el coco
• Kirchner, RB "El problema generalizado del coco". Amer. Math. Monthly 67, 516-519, 1960.
• Fadiman, Clifton (1962). La urraca matemática , Simon & Schuster
• Bogomolny, Alexander (1996) Cocos negativos al cortar el nudo

Enlaces externos

• Monos y cocos – Vídeo de Numberphile
• Cocos, una copia de la historia tal como apareció en el Saturday Evening Post
• El mono y los cocos: una introducción al algoritmo euclidiano extendido