El mono y los cocos es un acertijo matemático en el campo del análisis diofantino que se originó en un cuento de ficción de una revista que involucra a cinco marineros y un mono en una isla desierta que dividen un montón de cocos ; el problema es encontrar el número de cocos en la pila original (no se permiten cocos fraccionados). El problema es conocido por su dificultad confusa para los solucionadores de acertijos poco 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 la pila en cinco pilas iguales, le da el que queda sobre el coco a un mono que pasa y le quita su parte. El segundo entonces repite el procedimiento, dividiendo la pila restante en cinco y quitando su parte, al igual que el tercero, cuarto y quinto, cada uno de ellos encuentra un coco sobrante al dividir la pila por cinco, y se lo da a un mono. Finalmente, el grupo divide los cocos restantes en cinco montones iguales: esta vez no quedan cocos.
- ¿Cuántos cocos había en la pila original?
El mono y los cocos es el representante más conocido de una clase de problemas de rompecabezas 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 cierto número de partes iguales, posiblemente con un recordatorio. El problema es tan conocido que a menudo se hace referencia a toda la clase en términos generales como "problemas del tipo de los monos y los cocos", 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ántos, pero después de agregar un noveno y un undécimo, se dividió en 3 sacos, cada uno con un número entero de libras. ¿Cuántas libras de cemento? tenía yo? "
Los problemas piden la cantidad inicial o terminal. Expresado o implícito es el número positivo más pequeño que podría ser una solución. Hay dos incógnitas en tales 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. Común a la clase es la naturaleza de la ecuación resultante, que es una ecuación diofántica lineal en dos incógnitas. La mayoría de los miembros de la clase están determinados, pero algunos no (el mono y los cocos es uno de estos últimos). Los métodos algebraicos familiares son inútiles para resolver tales 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 restos específicos. [1] Eso haría que los problemas de los progenitores tengan más de 1000 años antes de su resurgimiento en la era moderna. Los problemas relacionados con la división que invocan el teorema del resto chino 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, 2 cuando se divide por 3, 5, 7 respectivamente. Diofanto de Alejandría estudió por primera vez problemas que requerían soluciones enteras en el siglo III d.C. El algoritmo euclidiano para el máximo común divisor que subyace a la solución de tales problemas fue descubierto por el geómetra griego Euclides y publicado en sus Elementos en 300CE.
El profesor David Singmaster , un historiador de acertijos, rastrea una serie de problemas relacionados menos plausiblemente a lo largo de la Edad Media, con algunas referencias que se remontan al imperio babilónico alrededor del 1700 a. C. Implican el tema general de sumar o restar fracciones de una pila o números específicos de objetos discretos y preguntar cuántos podrían haber sido al principio. La siguiente referencia a un problema similar se encuentra en Jacques Ozanam 's reconstrucciones mathématiques et físicos , 1725. En el campo de las matemáticas puras, Lagrange en 1770 expuso su continuo teorema fracción y lo aplicó a la solución de ecuaciones diofánticas.
La primera descripción del problema cercana a su redacción moderna apareció en los diarios del matemático y autor Lewis Carroll ("Alicia en el país de las maravillas") en 1888, que involucraba un montón de nueces sobre una mesa dividida en serie por cuatro hermanos, cada vez con el resto de uno dado a un mono, y la división final sale pareja. El problema nunca apareció en ninguna de las obras publicadas del autor, aunque desde otras referencias parece que el problema estaba en circulación en 1888. Un problema casi idéntico pronto apareció en WW Rouse Bola 's álgebra elemental , 1890. Tal proximidad sugiere una fuente común; La diseminación del problema puede haber ocurrido a través de los intercambios de Carroll con Bartholomew Price , profesor de matemáticas y amigo y tutor de Carroll . Existían cuatro versiones del problema: dos formas, una con restos de una y otra con restos de cero pero descartando nueces después de la división, y dos terminaciones, una donde la división final tiene un resto y otra donde sale par (o sin nueces se descartan). El problema fue mencionado en trabajos de matemáticos de época, con soluciones, en su mayoría erróneas, lo que indica que el problema era nuevo y desconocido en ese momento.
El dispositivo de objetos marcados (ver Cocos azules, más abajo) para ayudar a conceptualizar la división con residuos apareció por primera vez en 1912 en la obra de Norman H. Anning que involucraba un contenedor de manzanas dividido por tres hombres.
El problema se hizo notorio cuando el novelista y cuentista estadounidense Ben Ames Williams modificó un problema anterior y lo incluyó en una historia, "Cocos", en la edición del 9 de octubre de 1926 de The Saturday Evening Post . [2] Así es como Williams planteó el problema (condensado y parafraseado):
- Cinco hombres y un mono naufragaron en una isla. Pasaron el primer día recolectando cocos. Durante la noche, un hombre se despertó y decidió tomar su parte de los cocos. Los dividió en cinco montones. Le sobró un coco, así que se lo dio al mono, luego escondió su parte, volvió a juntar el resto y se volvió a dormir.
- Pronto, un segundo hombre se despertó e hizo lo mismo. Después de dividir los cocos en cinco montones, sobró un coco que le dio al mono. Luego escondió su parte, volvió a juntar el resto y volvió a la cama. El tercer, cuarto y quinto hombre siguió exactamente el mismo procedimiento. A la mañana siguiente, después de que todos se despertaron, dividieron los cocos restantes en cinco partes iguales. Esta vez no sobraron cocos.
- ¿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 respuesta al problema. El editor del Post, Horace Lorimer , disparó un telegrama a Williams diciendo: "POR EL AMOR DE MIKE, ¿CUÁNTOS COCOS? EL INFIERNO ESTÁ LLEGANDO AQUÍ". Williams siguió recibiendo cartas pidiendo una solución o proponiendo nuevas durante los próximos veinte años. [3]
Martin Gardner presentó el problema en su columna Mathematical Games de abril de 1958 en Scientific American . Dijo que Williams había modificado un problema anterior 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 pareja. 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] tanto que luego decidió convertirlo en el primer capítulo de su colección de "las mejores columnas", The Colossal Book of Mathematics . [3] Dijo que El mono y los cocos es "probablemente el rompecabezas Diofantino 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 se reimprimió en su totalidad en la antología de Clifton Fadiman de 1962 The Mathematical Magpie , [7] un libro que la Asociación Matemática de América recomienda para su adquisición por bibliotecas de matemáticas de pregrado. [8]
En la literatura han aparecido numerosas variantes que varían el número de marineros, monos o el número de cocos otorgados a los monos. [9]
Soluciones
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" requerida 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 algebraicamente 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 un y b . [10] Según la identidad de Bézout , la ecuación se puede resolver si y solo si d divide a c . Si es así, la ecuación tiene infinitas soluciones periódicas de la forma
- x = x 0 + t · b ,
- y = y 0 + t · a
donde ( x 0 , y 0 ) es una solución y t es un parámetro que puede ser cualquier número entero. No se pretende que el problema se resuelva mediante prueba y error; existen métodos deterministas para resolver ( x 0 , y 0 ) en este caso (ver texto).
Se han publicado numerosas soluciones a partir de 1928 tanto para el problema original como para la modificación de Williams. [11] [12] [13] [14] Se han ideado soluciones ingeniosas y concisas que utilizan congruencias de módulo, tamices y bases de números alternativos basadas en parte o principalmente en la definición recursiva del problema, una estructura que no será aplicable en el caso general. Las soluciones positivas más pequeñas para ambas versiones son lo suficientemente grandes como para que el ensayo y error sea muy probable que sea infructuoso. Se introdujo un ingenioso concepto de cocos negativos que resuelve fortuitamente el problema original. Las soluciones formalistas se basan en el algoritmo de Euclides aplicado a los coeficientes diofánticos. Finalmente, el cálculo de diferencias finitas produce una solución general parametrizada para cualquier número de marineros y todos los múltiplos de cocos que podrían haber estado en la pila original. En los tiempos modernos, una búsqueda de fuerza bruta por computadora sobre los números enteros positivos arroja rápidamente la solución.
Antes de abordar una solución al problema, cabe señalar un par de cosas. Si no hay residuos, dado que hay 6 divisiones de 5, 5 6 = 15,625 cocos deben estar en la pila; en la 6ª y última división, cada navegante recibe 1024 cocos. Ningún número positivo menor dará como resultado que las 6 divisiones salgan pares. Eso significa que en el problema tal como se indicó, se puede agregar cualquier múltiplo de 15,625 a la pila y satisfará las condiciones del problema. Eso también significa que la cantidad de cocos en la pila original es menor que 15,625; de lo contrario, restando 15,625 producirá una solución más pequeña. 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 de cientos o miles. A diferencia del ensayo y error en el caso de adivinar una raíz polinomial, el ensayo y error para una raíz diofántica no dará como resultado una convergencia obvia. No hay una forma sencilla de estimar cuál será la solución.
La versión original
Martin Gardner presentó un análisis resumido tanto del problema original como de la versión de William cuando presentó el problema en su columna Juegos matemáticos. Gardner comienza resolviendo el problema original porque es menos confuso que la variación de Williams. Sea N el tamaño de la pila original y F el número de cocos que recibió cada marinero después de la división final en 5 partes iguales por la mañana. Entonces, el número de cocos que quedan antes de la división de la mañana es F · 5 + 1. Si esa cantidad se designa como n , el número restante antes de la división del último marinero es:
invirtiendo el procedimiento del marinero durante la noche. Pero cada marinero siguió el mismo procedimiento; Por tanto, se define una serie recursiva de 5 taless (reemplazando con y generando una nueva ), el quinto y último de los cuales es el propio N , el número de cocos antes de la división por parte del primer marinero. Sustituyendo sucesivamente elarena rinde:
que se reduce a la ecuación diofántica: [3]
Según un teorema fundamental, esta ecuación tiene una solución si y solo si 11529 es un múltiplo del máximo común divisor de 1024 y 15625. 1024 = 4 5 y 15625 = 5 6 , por lo que su MCD es 1 y 11529 es un múltiplo de 1 por lo que la ecuación se puede resolver.
Gardner señala que esta ecuación es demasiado difícil de resolver mediante prueba y error. [15] Además, tiene un número infinito de soluciones. Pero Gardner estaba equivocado acerca de la dificultad. De hecho, si (N, F) es una solución, entonces también lo es (N + 15625 t, F + 1024 t) para cualquier número entero t . Esto significa que la ecuación también tiene soluciones en números enteros negativos. Al probar algunos números negativos pequeños, resulta que N = -4 y F = -1 es una solución. [16] Se trata de la absurda noción de cocos negativos; así que sumamos 15625 a -4 y 1024 a -1 para obtener la solución positiva más pequeña (15621, 1023) . [17]
Versión de Williams
El enfoque negativo de los cocos no se aplica a la versión de Williams, al menos no para una versión razonablemente pequeña | N |, 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 para que un poco de ensayo y error 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 en la pila original.
Si F es el número de cocos que recibe cada navegante en la división final de la mañana, el montón de la mañana es 5 F , que también debe ser divisible por 4, ya que el último navegante de la noche combinó 4 pilas para la división de la mañana. Así que la pila de la mañana, llame 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ó por 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 un múltiplo de 20 que dé como resultado una pila divisible por 4 antes de que se despierte el último marinero. Sucede que 3 * 20 = 60 funciona para dos marineros: aplicar la fórmula de recursividad para n dos veces da como resultado 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 el despertar de 3 marineros, la pila podría haber sido de 121 cocos. Pero 121 no es divisible por 4, por lo que para que 4 marineros se despierten, es necesario dar otro salto. En este punto, la analogía se vuelve obtusa, porque para acomodar el despertar de 4 marineros, el montón de la mañana debe ser un múltiplo de 60: si uno es persistente, se puede descubrir que 17 * 60 = 1020 funciona y el número mínimo en la pila original sería 2496. Una última iteración en 2496 para el despertar de 5 marineros, es decir, 5/4 (2496) +1 lleva la pila original a 3121 cocos.
Cocos azules
Otro dispositivo anterior al problema es utilizar objetos extra o marcados, en este caso cocos azules, para aclarar el proceso de división. Supongamos que el primer marinero antes de la división agrega cuatro cocos azules a la pila para garantizar la división entre 5 (ya que sabemos que incluso si no lo hace, habrá un resto de 1, por lo que sumar 4 hace que la pila sea divisible por 5). Divide la pila, toma el quinto con un coco extra (que no sea azul) que le lanza al mono, esconde su parte, luego vuelve a juntar el resto, dejando los 4 cocos azules a un lado. Cada marinero hace lo mismo. Después del quinto marinero (o después de la división de la mañana si hay un resto allí), los cocos azules se dejan a un lado, que no pertenecen a nadie. Dado que la pila original se divide 5 veces (o 6, si hay un resto en la mañana), incluidos los cocos azules, debe haber sido 5 5 (5 6 ) cocos. Eso hace que la pila 3125-4 = 3121 (15625-4 = 15621) cocos. Los cocos azules pueden considerarse cocos "virtuales" que no juegan ningún papel en el problema, sólo sirven para aclarar la divisibilidad. [18]
Numeración base 5
Una solución simple y obvia aparece cuando las divisiones y restas se realizan en base 5. Considere la resta, cuando el primer marinero toma su parte (y la del mono). Sea n 0 , n 1 , ... representar los dígitos de N, el número de cocos en la pila original, y s 0 , s 1 ... representan los dígitos de la parte S del marinero, ambos en base 5. Después del mono compartir, el dígito menos significativo de N ahora debe ser 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 (se desconoce el número real de dígitos en N y S, pero son irrelevantes en este momento):
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 restado de 0 base 5 para obtener 1 es 4, por lo que s 0 = 4. Pero como S es (N-1) / 5, y dividir entre 5 5 es simplemente desplazar el número una posición a la derecha, n 1 = s 0 = 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
Dado que 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 lanzarle 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
Tomar prestado 1 de n 1 (que ahora es 4) deja 3, por lo que s 1 debe ser 4 y, por lo tanto, n 2 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 2 y n 3 también son 4, etc. Hay 5 divisiones; los primeros 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 salga par (en 5). Entonces, hay cuatro 4 en N siguiendo un LSD de 1: N = 44441 5 = 3121 10
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 de la pila original de la siguiente manera:
- N => 4 (N – 1) / 5 o equivalentemente, N => 4 (N + 4) / 5 - 4.
Repetir esta transición 5 veces da 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
Dado que 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, entonces N = 3125 - 4 = 3121; el número que queda en la mañana llega a 1020, que es divisible uniformemente por 5 según sea necesario.
Congruencia de módulo
Se puede obtener una solución simple y sucinta utilizando directamente la estructura recursiva del problema: había cinco divisiones de los cocos en quintos, cada vez con uno sobrante (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 hubiera una de esas divisiones, 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 uno. división. [19]
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, la cantidad 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 el resto 1. Si hay 5 divisiones, entonces múltiplos de 5 5 = 3125 son obligatorios; el número más pequeño 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 probar que la pila restante es divisible por n , una propiedad de la que el creador del problema hizo un uso conveniente.
Una forma formal de enunciar el argumento anterior es:
La pila de cocos original 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 el número de frutos secos en la misma clase de congruencia (mod 5). Entonces,
- (mod 5) (el –1 es la nuez lanzada al mono)
- (mod 5)
- (mod 5) (–4 es la clase de congruencia)
Entonces, si comenzamos en el módulo de clase –4, nueces, entonces permaneceremos en el módulo de la clase –4. Como finalmente 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 entre las 5 de la mañana. Esta solución esencialmente invierte cómo se construyó (probablemente) el problema.
La ecuación diofántica y formas de solución
La ecuación diofántica equivalente para esta versión es:
- (1)
donde N es el número original de cocos y F es el número recibido por cada navegante en la división final de la mañana. Esto es solo trivialmente diferente de la ecuación anterior para el problema predecesor, y la capacidad de solución está garantizada por el mismo razonamiento.
Reordenando,
- (2)
Esta ecuación diofántica tiene una solución que se sigue directamente del algoritmo euclidiano ; de hecho, tiene infinitas soluciones periódicas positivas y negativas. Si (x 0 , y 0 ) es una solución de 1024x-15625y = 1, entonces N 0 = x 0 · 8404, F 0 = y 0 · 8404 es una solución de (2), lo que significa cualquier solución debe tener la forma
- (3)
dónde es un parámetro arbitrario que puede tener cualquier valor integral.
Un enfoque reduccionista
Uno puede tomar ambos lados de (1) por encima del módulo 1024, por lo que
Otra forma de pensarlo es que para para ser un número entero, el RHS de la ecuación debe ser un múltiplo entero de 1024; esa propiedad no se modificará factorizando tantos múltiplos de 1024 como sea posible del RHS. Reduciendo ambos lados en múltiplos de 1024,
restando
factoring,
El RHS aún debe ser un múltiplo de 1024; dado que 53 es primo relativo a 1024, 5 F +4 debe ser un múltiplo de 1024. El múltiplo más pequeño de este tipo es 1 · 1024, por lo que 5 F + 4 = 1024 y F = 204. Sustituyendo en (1)
Algoritmo euclidiano
El algoritmo euclidiano es bastante tedioso, pero es una metodología general para resolver ecuaciones racionales ax + by = c que requiere respuestas integrales. De (2) anterior, es evidente que 1024 (2 10 ) y 15625 (5 6 ) 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 estos dos cantidades:
Primero, obtenga restos sucesivos hasta que GCD permanezca:
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 por 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 0 , F 0 ) = (-4776 · 8404, -313 * 8404); el mas pequeño (ver (3) en la subsección anterior) que hará que tanto N como F sean positivos es 2569, entonces:
Fracción continua
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 ]; [20] su convergente termina después de que la repetición es 313 ⁄ 4776 , lo que nos da x 0 = –4776 e y 0 = 313. El valor mínimo de t para el que tanto N como F no son negativos es 2569, por lo que
- .
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, déjelo ser , 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 .
El primer paso es obtener una expansión algebraica de la relación de recurrencia correspondiente a la transformación del pilote de cada marinero, siendo el número dejado por el marinero:
dónde , el número originalmente reunido, y el número que queda por la mañana. Expandiendo la recurrencia sustituyendo por veces rinde:
Factorizando el último término,
El polinomio de la serie de potencias entre paréntesis de la forma sumas a entonces,
que se simplifica a:
Pero es el número que queda por la mañana, que es un múltiplo de (es decir , el número asignado a cada marinero por la mañana):
Resolviendo para (=),
La ecuación es una ecuación diofántica lineal en 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.
Ahora se aplican las consideraciones de la teoría numérica. Para para ser un número entero, es suficiente que ser un número entero, así que déjalo ser :
La ecuación debe transformarse en la forma cuyas soluciones son fórmulas. Por eso:
- , dónde
Porque y son relativamente primos, existen soluciones enteras por la identidad de Bézout. Esta ecuación se puede reformular como:
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 0 = 1 si m es impar y r 0 = –1 si m es par es una solución.
La identidad de Bézout da la solución periódica , así que sustituyendo en la ecuación diofántica y reordenando:
dónde por extraño y por incluso y es cualquier número entero. [21] Por un hecho, el más pequeño positivo será elegido de tal manera que satisface las restricciones del enunciado del problema.
En la versión del problema de William, son 5 marineros, entonces es 1, y puede tomarse como cero para obtener la respuesta positiva más baja, por lo que N = 1 · 5 5 - 4 = 3121 para el número de cocos en la pila original. (Puede observarse 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 un solución negativa de pequeña magnitud).
Aquí hay una tabla de soluciones positivas. para los primeros ( es cualquier número entero no negativo):
2 | [22] |
3 | |
4 | |
5 | |
6 | |
7 | |
8 |
Otras variantes y soluciones generales
Otras variantes, incluido el supuesto problema predecesor, tienen soluciones generales relacionadas para un número arbitrario de marineros.
Cuando la división de la mañana también tiene un resto de uno, la solución es:
Para y esto arroja 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 salían iguales y las nueces (o artículos) se asignaban de la pila restante después de la división. En estas formas, la relación de recursividad es:
La forma alternativa también tenía dos finales, cuando la división matutina sale pareja y cuando queda una nuez para el mono. Cuando la división de la mañana sale uniforme, la solución general se reduce mediante una derivación similar a:
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 por la mañana, por lo que la división final sale incluso sin coco sobrante .
Cuando la división de la mañana da como resultado una nuez sobrante, la solución general es:
dónde Si es extraño, y Si incluso. 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 a la división final le queda un coco para el mono.
Otras variantes posteriores a Williams que especifican diferentes residuos, incluidos los positivos (es decir, el mono agrega cocos a la pila), se han tratado en la literatura. La solucion es:
dónde por extraño y por incluso, 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 añaden cocos a la pila).
Otras variantes en las que el número de hombres o el resto varían entre divisiones, generalmente están fuera de la clase de problemas asociados con el mono y los cocos, aunque de manera similar se reducen a ecuaciones diofánticas lineales en dos variables. Sus soluciones ceden a las mismas técnicas y no presentan nuevas dificultades.
Ver 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
- ^ CRONOLOGÍA DE LAS MATEMÁTICAS RECREATIVAS por David Singmaster [1]
- ↑ a b Pleacher (2005)
- ↑ a b c Gardner (2001)
- ↑ Antonick (2013)
- ↑ Antonick (2013): "Luego le pregunté a Jim si su padre tenía un rompecabezas favorito, y respondió casi de inmediato: 'Los monos [ sic ] y los cocos. Le gustaba mucho ese'".
- ^ Wolfram Mathworld
- ^ REVISIÓN DE KIRKUS de La urraca matemática 27 de julio de 1962
- ^ La urraca matemática , de Clifton Fadiman, Asociación matemática de América, Springer, 1997
- ^ Pappas, T. "El mono y los cocos". La alegría de las matemáticas. San Carlos, CA: Wide World Publ./Tetra, págs. 226-227 y 234, 1989.
- ^ d se puede encontrar si es necesario a través del algoritmo de Euclid
- ^ Underwood, RS y Robert E. Moritz. "3242." El American Mathematical Monthly 35, no. 1 (1928): 47-48. doi: 10.2307 / 2298601.
- ^ Kirchner, Roger B. "El problema generalizado del coco", The American Mathematical Monthly 67, no. 6 (1960): 516-19. doi: 10.2307 / 2309167.
- ^ S. Singh y D. Bhattacharya, "Sobre la división de cocos: un problema diofantino lineal", The College Mathematics Journal, mayo de 1997, págs. 203–4
- ^ G. Salvatore y T. Shima, "De cocos e integridad", Crux Mathematicorum, 4 (1978) 182-185
- ^ Gardner (2001) p. 4: "La ecuación es demasiado difícil de resolver por ensayo y error, y aunque existe un procedimiento estándar para resolverla mediante el uso ingenioso de fracciones continuas, el método es largo y tedioso".
- ^ Bogomolny (1996)
- ^ Gardner (2001) p. 5: "Esta solución a veces se atribuye al físico de la Universidad de Cambridge PAM Dirac (1902-1984), pero en respuesta a mi consulta, el profesor Dirac escribió que obtuvo la solución de JHC Whitehead, profesor de matemáticas (y sobrino del famoso filósofo ). El profesor Whitehead, respondiendo a una consulta similar, dijo que la obtuvo de otra persona y que no he seguido con el asunto ".
- ↑ Una ilustración más simple del dispositivo es un problema anterior de un hombre que entrega 17 caballos a sus tres hijos, especificando que el hijo mayor recibe la mitad, el siguiente un tercero y el menor un noveno. Los hijos están confundidos, por lo que consultan a un comerciante de caballos sabio. Él dice, "aquí, toma mi caballo". Los hijos dividen debidamente los caballos, descubriendo que todas las divisiones salen iguales, con un caballo sobrante, que devuelven al comerciante.
- ^ 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 se hagan, la pila restante contendrá -4 cocos. Esta es una anomalía matemática llamada "punto fijo". Solo unos pocos problemas tienen ese punto, pero cuando lo hay, hace que el problema sea mucho más fácil de resolver. Todas las soluciones al problema son múltiplos de 5 sumados o restados del punto fijo.
- ^ Vea aquí una exposición del método.
- ↑ Gardner da una formulación equivalente pero bastante críptica al elegir inexplicablemente la no canónica Cuándo es par, luego refactorizando la expresión de una manera que oscurezca la periodicidad:
- por impar,
- por incluso,
- ^ Si bien 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
- Abogado, David (2005). Problema de la semana: el mono y los cocos 16 de mayo de 2005
- Gardner, Martin (2001). El colosal libro de las matemáticas: acertijos clásicos, paradojas y problemas WW Norton & Company; ISBN 0-393-02023-1
- Pappas, Theoni (1993). Joy of Mathematics: Descubriendo las matemáticas por todos lados | Wide World Publishing, 23 de enero de 1993, ISBN 0933174659
- Wolfram Mathworld: Problema del mono y el coco
- Kirchner, RB "El problema generalizado del coco". Amer. Matemáticas. Mensual 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 - Video de Numberphile
- Coconuts , una copia de la historia tal como apareció en el Saturday Evening Post