Opice a kokosové ořechy - The monkey and the coconuts

Opice a kokosové ořechy je matematická hádanka v oblasti diofantické analýzy, která vznikla v časopisecké smyšlené povídce zahrnující pět námořníků a opici na pustém ostrově, kteří rozdělili hromadu kokosových ořechů ; problém je zjistit počet kokosových ořechů v původní hromadě (zlomkové kokosové ořechy nejsou povoleny). Problém je pověstný svou matoucí obtížností pro nenáročné řešitele hádanek, i když při správném matematickém přístupu je řešení triviální. Problém se stal základem sbírek rekreační matematiky .

Obecný popis

Problém lze vyjádřit takto:

Je tu hromada kokosových ořechů, kterou vlastní pět mužů. Jeden muž rozdělí hromádku na pět stejných hromádek, přičemž jeden zbylý nad kokosem projde procházející opici a odnáší si vlastní podíl. Druhý muž pak postup zopakuje, zbylou hromádku rozdělí na pět a odebere svůj podíl, stejně jako třetí, čtvrtou a pátou, přičemž každý z nich najde jeden kokos, který zbyl při dělení hromádky pěti a dá ji opice. Nakonec skupina rozdělí zbývající kokosové ořechy na pět stejných hromádek: tentokrát nezůstanou žádné kokosové ořechy.

Kolik kokosových ořechů bylo na původní hromadě?

Opice a kokosové ořechy jsou nejznámějším zástupcem třídy hádankových úloh vyžadujících celočíselná řešení strukturovaná jako rekurzivní dělení nebo frakcionace nějakého diskrétně dělitelného množství, se zbytky nebo bez nich, a konečné rozdělení na určitý počet stejných částí, případně s zbytek. Problém je tak dobře známý, že celá třída je často široce označována jako „problémy typu opice a kokosu“, ačkoli většina s tímto problémem úzce nesouvisí.

Další příklad: „Mám celé množství liber cementu, nevím kolik, ale po přidání devátého a jedenáctého bylo rozděleno na 3 pytle, každý s celým počtem liber. Kolik liber cementu měl jsem? "

Problémy vyžadují počáteční nebo koncové množství. Uvedené nebo implikované je nejmenší kladné číslo, které by mohlo být řešením. V takových problémech existují dvě neznámé, počáteční číslo a koncové číslo, ale pouze jedna rovnice, která je algebraickou redukcí výrazu pro vztah mezi nimi. Společné pro třídu je povaha výsledné rovnice, což je lineární diofantická rovnice ve dvou neznámých. Většina členů třídy je rozhodná, ale někteří ne (opice a kokosové ořechy jsou jedni z druhých). Známé algebraické metody jsou pro řešení takových rovnic nedostačující.

Dějiny

Původ třídy těchto problémů je přisuzován indickému matematikovi Mahāvīrovi v kapitole VI, §131 1 / 2 , 132 1 / 2 jeho Ganita-sara-sangraha („Kompendium esence matematiky“), kolem 850 n. L. , která se zabývala sériovým dělením ovoce a květin s určenými zbytky. To by způsobilo, že problémy předků budou staré více než 1000 let, než se v moderní době znovu objeví. Problémy zahrnující rozdělení, které vyvolávají čínskou zbytkovou větu, se objevily v čínské literatuře již v prvním století n. L. Sun Tzu se zeptal: Najděte číslo, které při dělení 3, 5 a 7 ponechá zbytky 2, 3 a 2. Diophantus z Alexandrie poprvé studoval problémy vyžadující celočíselná řešení ve 3. století n. L. Euclidean algoritmus pro největší společný dělitel, který je základem řešení takových problémů byla objevena řecký geometr Euclid a publikoval v jeho prvků v 300CE.

Prof. David Singmaster , historik hádanky, sleduje řadu problémů méně věrohodně spojených přes středověku, s několika odkazy jako daleká záda jako babylónské říše circa 1700BC. Zahrnují obecné téma sčítání nebo odčítání zlomků hromady nebo konkrétního počtu diskrétních objektů a ptát se, kolik jich mohlo být na začátku. Další odkaz na podobný problém je v Jacques Ozanam 's Récréations mathématiques et physiques , 1725. V oblasti čisté matematiky Lagrange v roce 1770 vysvětlil svou pokračující zlomkovou větu a aplikoval ji na řešení diofantických rovnic.

První popis problému v blízkosti jeho moderního znění se objevil v denících matematika a autora Lewise Carrolla („Alice in Wonderland“) v roce 1888, zahrnující hromadu ořechů na stole sériově rozděleném čtyřmi bratry, pokaždé s zbytek jedné opice a finální rozdělení vyjde rovnoměrně. Problém nikdy se objevil v některém z autorových publikovaných prací, i když z jiných odkazů se zdá, že problém byl v oběhu v roce 1888. Téměř totožný problém brzy objevil v WW Rouse ples ‚s Elementary algebry , 1890. Taková blízkost navrhuje společný zdroj; k šíření problému mohlo dojít prostřednictvím Carrollových výměn s Bartholomewem Priceem , profesorem matematiky a Carroliným přítelem a vychovatelem. Existovaly čtyři ztvárnění problému: dvě formy, jedna se zbytky jedné a druhá se zbytky nuly, ale matice vyřazené po rozdělení, a dvě koncovky, jedna, kde konečná divize má zbytek a druhá, kde vychází rovnoměrně (nebo žádné ořechy jsou vyřazeny). Problém byl zmíněn v pracích dobových matematiků, přičemž řešení byla většinou špatná, což naznačuje, že problém byl v té době nový a neznámý.

Zařízení označených předmětů (viz níže Modré kokosové ořechy níže) na pomoc při konceptualizaci rozdělení se zbytky se poprvé objevilo v roce 1912 v díle Normana H. Anninga zahrnujícího popel jablek rozdělený třemi muži.

Tento problém se stal notoricky známým, když americký romanopisec a autor povídek Ben Ames Williams upravil starší problém a zahrnoval jej do příběhu „Kokosové ořechy“ ve vydání Saturday Evening Post z 9. října 1926 . Zde je problém, který Williams uvedl (zhuštěný a parafrázovaný):

Na ostrově ztroskotalo pět mužů a opice. První den strávili sbíráním kokosů. V noci se jeden muž probudil a rozhodl se vzít si svůj podíl z kokosových ořechů. Rozdělil je na pět hromádek. Zbýval jeden kokosový ořech, takže ho dal opici, pak schoval svůj podíl, zbytek dal dohromady a šel spát.

Brzy se probudil druhý muž a udělal to samé. Po rozdělení kokosových ořechů na pět hromádek zbyl jeden kokosový ořech, který dal opici. Poté svůj podíl schoval, zbytek dal dohromady a vrátil se do postele. Třetí, čtvrtý a pátý muž postupovali přesně stejným způsobem. Druhý den ráno, když se všichni probudili, rozdělili zbývající kokosové ořechy na pět stejných podílů. Tentokrát nezůstaly žádné kokosové ořechy.

Kolik kokosových ořechů bylo na původní hromadě?

Williams do příběhu nezahrnul odpověď. Časopis byl zaplaven více než 2 000 dopisy, které prosily o odpověď na problém. Redaktor příspěvku Horace Lorimer skvěle vypálil telegram Williamsovi: „ZA LÁSKU MIKE, KOLIK KOKOSŮ? Williamsová dostávala dopisy s žádostí o řešení nebo navrhováním nových po dobu dalších dvaceti let.

Martin Gardner představoval problém v jeho dubnu 1958 Matematické hry sloupce v časopise Scientific American . Uvedl, že Williams upravil starší problém, aby byl více matoucí. Ve starší verzi je kokos pro opici na konečné divizi; ve Williamsově verzi finální rozdělení ráno vychází rovnoměrně. Dostupné historické důkazy ale nenaznačují, ke kterým verzím měl Williams přístup. Gardner kdysi řekl svému synovi Jimovi, že je to jeho oblíbený problém, a to natolik, že se později rozhodl z něj udělat první kapitolu své sbírky „best of columns“, The Colossal Book of Mathematics . Řekl, že Opice a kokosové ořechy jsou „pravděpodobně nejpracovanější a nejméně často řešenou“ diofantinovou hádankou. Od té doby se Williamsova verze problému stala základem rekreační matematiky . Původní příběh obsahující problém byl plně přetištěn v antologii Cliftona Fadimana z roku 1962 Matematická straka , kniha, kterou Matematická asociace Ameriky doporučuje k získání vysokoškoláckými matematickými knihovnami.

V literatuře se objevilo mnoho variant, které mění počet námořníků, opic nebo počet kokosových ořechů.

Řešení

Byla publikována řada řešení počínaje rokem 1928 jak pro původní problém, tak pro Williamsovu úpravu. Chytrá a stručná řešení využívající modulo kongruence, síta a alternativní číselné základny byla navržena na základě částečně nebo většinou rekurzivní definice problému, struktury, která nebude v obecném případě použitelná. Nejmenší pozitivní řešení obou verzí jsou dostatečně velká na to, aby pokusy a omyly byly velmi pravděpodobně bezvýsledné. Byl představen důmyslný koncept negativních kokosových ořechů, který náhodně řeší původní problém. Formalistická řešení jsou založena na Euclidově algoritmu aplikovaném na diofantické koeficienty. Nakonec počet konečných rozdílů poskytuje parametrizované obecné řešení pro libovolný počet námořníků a všechny násobky kokosových ořechů, které mohly být na původní hromadě. V moderní době poskytuje řešení řešení pomocí počítačové hrubé síly přes kladná celá čísla.

Než se pustíte do řešení problému, je třeba poznamenat několik věcí. Pokud nebyly žádné zbytky, bylo dáno 6 divizí po 5, 5 ⁶ = na hromádce musí být 15 625 kokosových ořechů; na 6. a poslední divizi dostane každý námořník 1024 kokosových ořechů. Žádné menší kladné číslo bude mít za následek rovnoměrné vycházení všech 6 divizí. To znamená, že v problému, jak je uvedeno, může být na hromádku přidán jakýkoli násobek 15 625 a splní problémové podmínky. To také znamená, že počet kokosových ořechů v původní hromadě je menší než 15 625, jinak odečtením 15 625 získáte menší řešení. Ale číslo na původní hromádce není triviálně malé, například 5 nebo 10 (proto je to těžký problém) - může se pohybovat ve stovkách nebo tisících. Na rozdíl od pokusu a omylu v případě uhodnutí polynomiálního kořene nebude mít pokus a omyl u diofantického kořene za následek zjevnou konvergenci. Neexistuje jednoduchý způsob, jak odhadnout, jaké bude řešení.

Původní verze

Souhrnnou analýzu původního problému a Williamovy verze představil Martin Gardner, když problém představil ve svém sloupku Matematické hry. Gardner začíná řešením původního problému, protože je méně matoucí než variace Williams. Nechť N je velikost původní hromady a F je počet kokosových ořechů, které každý námořník obdržel po konečném rozdělení na 5 stejných podílů ráno. Potom počet kokosových ořechů, které zbyly před ranním dělením, je F  · 5+1. Pokud je toto množství označeno n , zbývá do posledního námořnického oddílu počet:

${\ Displaystyle n '= n \ cdot {\ tfrac {5} {4}}+1}$

obrácení postupu námořníka během noci. Každý námořník však postupoval stejným způsobem; jsou tak definovány rekurzivní sérii 5 takových s (nahrazující s a vygenerování nového ), pátý a poslední z nich je N sám, počet kokosové ořechy před rozdělením se první námořník. Postupně Dosazením ů a výnosy: ${\ displaystyle n '}$${\ displaystyle n}$${\ displaystyle n '}$${\ displaystyle n '}$${\ displaystyle n '}$${\ displaystyle n}$

${\ Displaystyle N = ((((((((F \ cdot 5+1) \ cdot {\ tfrac {5} {4}}+1) \ cdot {\ tfrac {5} {4}}+1) \ cdot { \ tfrac {5} {4}}+1) \ cdot {\ tfrac {5} {4}}+1) \ cdot {\ tfrac {5} {4}}+1}$

což redukuje na diofantinskou rovnici:

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

Podle základní věty má tato rovnice řešení právě tehdy, pokud je 11529 násobkem největšího společného dělitele 1024 a 15625. 1024 = 4 ⁵ a 15625 = 5 ⁶ , takže jejich GCD je 1 a 11529 je násobkem 1, takže rovnice je řešitelná.

Gardner poukazuje na to, že tuto rovnici je příliš obtížné vyřešit metodou pokusu a omylu. Navíc má nekonečné množství řešení. Gardner se ale v obtížnosti mýlil. Ve skutečnosti, pokud (N, F) je řešením, pak je (N + 15625 t, F + 1024 t) pro jakékoli celé číslo t . To znamená, že rovnice má také řešení v záporných celých číslech. Vyzkoušením několika malých záporných čísel se ukáže, že N = -4 a F = -1 je řešením. To zahrnuje absurdní představu negativních kokosových ořechů; tak sečteme 15625 až -4 a přidáme 1024 až -1, abychom získali nejmenší kladné řešení (15621, 1023) .

Williamsova verze

Negativní kokosový přístup se nevztahuje na verzi Williams, alespoň ne na přiměřeně malou | N |, takže je zapotřebí systematičtější přístup.

Pomocí síta

Prostor vyhledávání lze zmenšit řadou stále větších faktorů pozorováním struktury problému tak, aby trochu pokusů a omylů našlo řešení. Vyhledávací prostor je mnohem menší, pokud jeden začíná počtem kokosových ořechů přijatých každým mužem v ranní divizi, protože toto číslo je mnohem menší než číslo na původní hromádce.

Pokud F je počet kokosových ořechů, které každý námořník obdrží v konečné divizi ráno, hromada ráno je 5 F , což musí být také dělitelné 4, protože poslední námořník v noci spojil 4 hromádky pro ranní rozdělení. Ranní hromádka, volejte číslo n , je násobkem 20. Hromada před posledním probuzením námořníka musela být 5/4 ( n ) +1. Pokud se v noci probudil jen jeden námořník, pak 5/4 (20) +1 = 26 funguje na minimální počet kokosových ořechů v původní hromadě. Pokud se ale dva námořníci probudili, 26 není dělitelné 4, takže ranní hromádka musí být nějakým násobkem 20, což dává hromadu dělitelnou 4, než se probudí poslední námořník. Stává se, že 3*20 = 60 funguje pro dva námořníky: použití rekurzivního vzorce pro n dvakrát poskytne 96 jako nejmenší počet kokosových ořechů v původní hromadě. 96 je dělitelné 4 ještě jednou, takže pro 3 námořníky, kteří se probudili, mohla být hromada 121 kokosových ořechů. Ale 121 není dělitelné 4, takže pro probuzení 4 námořníků je třeba udělat další skok. V tomto okamžiku se analogie stává tupou, protože aby se ubytovali 4 námořníci, kteří se probouzejí, musí být ranní hromádka několikanásobkem 60: pokud je jeden vytrvalý, lze zjistit, že trik a minimální počet dělá 17*60 = 1020 v původní hromádce by bylo 2496. Poslední iterace 2496 pro probuzení 5 námořníků, tj. 5/4 (2496) +1 přináší původní hromádku na 3121 kokosových ořechů.

Modré kokosy

Dalším zařízením předcházejícím problému je použití extra nebo označených předmětů, v tomto případě modrých kokosových ořechů, k objasnění procesu dělení. Předpokládejme, že první námořník před divizí přidá na hromádku čtyři modré kokosové ořechy, aby bylo zaručeno dělení 5 (protože víme, i když ne, že zbude 1, takže přidáním 4 bude hromada dělitelná 5). Rozdělí hromádku, vezme pátou s extra (nemodrým) kokosem, který hodí opici, skryje svůj podíl, pak dá zbytek dohromady, čímž položí 4 modré kokosy na stranu. Každý námořník dělá to samé. Po pátém námořníkovi (nebo po rozdělení ráno, pokud je tam zbytek) zůstanou modré kokosové ořechy na boku, které nikomu nepatří. Protože je původní hromádka rozdělena 5krát (nebo 6, pokud zbývá ráno), včetně modrých kokosových ořechů, muselo to být 5 ⁵ (5 ⁶ ) kokosových ořechů. To dělá hromadu 3125-4 = 3121 (15625-4 = 15621) kokosových ořechů. Modré kokosové ořechy mohou být považovány za „virtuální“ kokosové ořechy, které v problému nehrají žádnou roli, pouze slouží k objasnění dělitelnosti.

Číslování základny 5

Jednoduché a zřejmé řešení se objeví, když jsou dělení a odčítání prováděny na základně 5. Zvažte odečtení, když první námořník vezme svůj podíl (a opičí). Nechť n ₀ , n ₁ , ... představují číslice N, počet kokosových ořechů na původní hromádce, a s ₀ , s ₁ ... představují číslice námořnického podílu S, oba základny 5. Po opičích podíl, nejméně významná číslice N musí být nyní 0; po odečtení musí být nejméně významná číslice N ', kterou zanechal první námořník, 1, tedy následující (skutečný počet číslic v N i S je neznámý, ale právě teď jsou irelevantní):

n5n4n3n2n1 0   (N5)
  s4s3s2s1s0   (S5)
          1   (N'5)

Číslice odečtená od 0 báze 5 do výtěžku 1 je 4, takže s ₀ = 4. Ale protože S je (N-1)/5 a dělení 5 ₅ je pouze posunutí čísla o jednu pozici vpravo, n ₁ = s ₀ = 4. Nyní tedy odčítání vypadá takto:

n5n4n3n2 4 0
  s4s3s2s1 4
          1  

Protože další námořník bude dělat totéž na N ', nejméně významná číslice N' se stane 0 po házení jedné opici a LSD ze S 'musí být 4 ze stejného důvodu; další číslice N 'musí být také 4. Takže teď to vypadá takto:

n5n4n3n2 4 0
  s4s3s2s1 4
        4 1 

Vypůjčení 1 z n ₁ (což je nyní 4) zanechá 3, takže s ₁ musí být 4, a tedy také n ₂ . Takže teď to vypadá takto:

n5n4n3 4 4 0
  s4s3s2 4 4
        4 1  

Ale stejné uvažování opět platí pro N 'jako pro N, takže další číslice N' je 4, takže s ₂ a n ₃ jsou také 4 atd. Existuje 5 divizí; první čtyři musí nechat na hromádce lichého čísla 5 na hromádce pro další divizi, ale poslední divize musí nechat sudou číselnou základnu 5, takže ranní rozdělení vyjde sudé (za 5 s). Existují tedy čtyři 4 v N po LSD 1: N = 44441 ₅ = 3121 ₁₀

Numerický přístup

Jednoduchá numerická analýza vypadá takto: Pokud N je počáteční číslo, každý z 5 námořníků přepne původní hromádku takto:

N => 4 (N – 1)/5 nebo ekvivalentně, N => 4 (N+4)/5 - 4.

Opakováním tohoto přechodu 5krát získáte číslo, které ráno zbývá:

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

Protože toto číslo musí být celé číslo a 1024 je relativně prvočíslo 3125, N+4 musí být násobkem 3125. Nejmenší takový násobek je 3125  · 1, takže N = 3125 - 4 = 3121; ráno zbývá číslo 1020, které je podle potřeby rovnoměrně dělitelné 5.

Modulová shoda

Jednoduché stručné řešení lze získat přímým využitím rekurzivní struktury problému: Bylo tam pět rozdělení kokosových ořechů na pětiny, pokaždé s jedním zbylým (odložení finálního dělení ráno). Hromada zbývající po každém rozdělení musí obsahovat integrální počet kokosových ořechů. Pokud by existovalo pouze jedno takové rozdělení, pak je zřejmé, že 5  · 1+1 = 6 je řešením. Ve skutečnosti je řešením jakýkoli násobek pěti plus jedna, takže možný obecný vzorec je 5  · k - 4, protože násobek 5 plus 1 je také násobkem 5 mínus 4. Takže pro jeden také funguje 11, 16 atd. divize.

Pokud jsou provedeny dvě dělení, musí být použit násobek  5,5 = 25 místo 5, protože 25 lze dělit 5 dvakrát. Takže počet kokosových ořechů, které by mohly být na hromadě, je k  · 25 - 4. k = 1, čímž se získá 21, je nejmenší kladné číslo, které lze postupně dělit 5 dvakrát zbytkem 1. Pokud existuje 5 divizí, pak násobky 5 ⁵ = 3125 jsou požadovány; nejmenší takové číslo je 3125 - 4 = 3121. Po 5 děleních zbývá 1020 kokosových ořechů, číslo dělitelné 5 podle problému. Po n děleních lze ve skutečnosti dokázat, že zbývající hromádka je dělitelná n , což je vlastnost, kterou tvůrce problému pohodlně využil.

Formální způsob vyjádření výše uvedeného argumentu je:

Původní hromada kokosových ořechů bude rozdělena 5 celkem 5krát se zbytkem 1, bez ohledu na poslední rozdělení ráno. Nechť N = počet kokosových ořechů v původní hromadě. Každá divize musí ponechat počet ořechů ve stejné třídě shody (mod 5). Tak,

${\ Displaystyle N \ equiv 4/5 \ cdot (N-1)}$ (mod 5) (–1 je matice hodená opici)

${\ displaystyle 5N \ equiv 4N-4}$ (mod 5)

${\ Displaystyle N \ equiv -4}$ (mod 5) (–4 je třída shody)

Pokud jsme tedy začali v modulo třídě –4 matice, pak zůstaneme ve třídě modulo –4. Protože nakonec musíme hromadu rozdělit 5krát nebo 5^5, původní hromada byla 5^5 - 4 = 3121 kokosových ořechů. Zbytek 1020 kokosových ořechů se pohodlně rovnoměrně rozdělí na 5 ráno. Toto řešení v podstatě obrací, jak byl problém (pravděpodobně) konstruován.

Diophantinova rovnice a formy řešení

Ekvivalentní diofantická rovnice pro tuto verzi je:

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

kde N je původní počet kokosových ořechů a F je počet, který každý námořník obdržel při konečné divizi ráno. To se jen triviálně liší od výše uvedené rovnice pro problém předchůdce a řešitelnost je zaručena stejným uvažováním.

Změna pořadí,

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

Tato diofantická rovnice má řešení, které vyplývá přímo z euklidovského algoritmu ; ve skutečnosti má nekonečně mnoho periodických řešení pozitivních i negativních. Pokud (x ₀ , y ₀ ) je řešení 1024x – 15625y = 1, pak N ₀ = x ₀  · 8404, F ₀ = y ₀  · 8404 je řešením (2), což znamená, že jakékoli řešení musí mít tvar

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

kde je libovolný parametr, který může mít libovolnou integrální hodnotu. ${\ displaystyle t}$

Redukcionistický přístup

Lze vzít obě strany (1) nad modulo 1024, takže

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

Další způsob uvažování o tom je, že aby bylo RHS rovnice celočíselné, musí být integrálním násobkem 1024; tento majetek se nezmění tak, že se z RHS odečte co nejvíce násobků 1024. Snížení obou stran o násobky 1024, ${\ displaystyle n}$

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

odčítání,

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

faktoring,

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

RHS musí být stále násobkem 1024; od 53 je relativně prvočíslo 1024, 5 F 4 musí být násobkem 1024. Nejmenší jako násobek 1  · 1024, takže 5 F + 4 = 1024, F = 204. Nahrazení do (1)

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

Euklidovský algoritmus

Euklidovský algoritmus je poměrně zdlouhavý, ale obecná metodika pro řešení racionálních rovnic ax+by = c vyžaduje integrální odpovědi. Z (2) výše je zřejmé, že 1024 (2 ¹⁰ ) a 15625 (5 ⁶ ) jsou relativně primární, a proto je jejich GCD 1, ale potřebujeme redukční rovnice pro zpětnou substituci, abychom získali N a F ve smyslu těchto dvou množství:

Nejprve získejte po sobě jdoucí zbytky, dokud nezůstane GCD:

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) (zbytek 1 je GCD 15625 a 1024)

1 = 10 - 3 (13–1 · 10) = 4 · 10 - 3 · 13 (změnit pořadí (g), nahradit 3 z (f) a spojit)

1 = 4 · (36 - 2 · 13) - 3 · 13 = 4 · 36 - 11 · 13 (náhrada za 10 od (e) a kombinace)

1 = 4 · 36 - 11 · (229 - 6 · 36) = –11 · 229 + 70*36 (náhrada za 13 z (d) a kombinace)

1 = –11 · 229 + 70 · (265 - 1 · 229) = –81 · 229 + 70 · 265 (náhrada za 36 od (c) a kombinace)

1 = –81 · (1024 - 3 · 265) + 70 · 265 = –81 · 1024 + 313 · 265 (náhrada za 229 z (b) a kombinace)

1 = –81 · 1024 + 313 · (15625 - 15 · 1024) = 313 · 15625 - 4776 · 1024 (náhrada za 265 od (a) a kombinace)

Takže dvojice (N ₀ , F ₀ ) = (-4776 · 8404, -313*8404); nejmenší (viz (3) v předchozím pododdíle), který bude dělat N i F kladný, je 2569, takže: ${\ displaystyle t}$

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

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

Pokračující zlomek

Alternativně lze použít pokračující zlomek, jehož konstrukce je založena na euklidovském algoritmu. Pokračující frakce pro 1024 / 15625 (0.065536 přesně) je [, 15,3,1,6,2,1, 3 ]; jeho konvergent ukončen po opakování je 313 / 4776 , což nám dává x ₀ = –4776 a y ₀ = 313. Nejmenší hodnota t, pro kterou jsou N i F nezáporná, je 2569, takže

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

Toto je nejmenší kladné číslo, které splňuje podmínky problému.

Zobecněné řešení

Když je počet námořníků parametrem, nechť jde spíše než o výpočetní hodnotu, pečlivá algebraická redukce vztahu mezi počtem kokosových ořechů v původní hromadě a počtem přiděleným každému námořníkovi v dopoledních hodinách poskytne analogický diofantický vztah, jehož koeficienty jsou výrazy v . ${\ displaystyle m}$${\ displaystyle m}$

Prvním krokem je získat algebraické rozšíření relace opakování odpovídající transformaci hromádky každého námořníka, což je číslo, které námořník zanechal: ${\ displaystyle n_ {i}}$

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

kde se původně shromáždilo číslo a číslo odešlo ráno. Rozšíření opakování substitucí pro časy výnosů: ${\ 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]}$

Když vezmeme v úvahu druhý termín,

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

Výkonová řada polynom v závorce tiskopisu částek, které mají tak, ${\ 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]}$

což zjednodušuje:

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

Ale zbývá ráno číslo, které je násobkem (tj . Číslo přidělené každému námořníkovi ráno): ${\ 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}}}}$

Řešení pro (= ), ${\ displaystyle n_ {0}}$${\ displaystyle N}$

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

Rovnice je lineární diofantickou rovnicí ve dvou proměnných a . je parametr, který může být libovolné celé číslo. Na povaze rovnice a způsobu jejího řešení nezávisí . ${\ displaystyle N}$${\ displaystyle F}$${\ displaystyle m}$${\ displaystyle m}$

Nyní platí úvahy o teoretických číslech. Aby to bylo celé číslo, stačí, aby to bylo celé číslo, takže nechme to být : ${\ 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}}}}$

Rovnice musí být transformována do formy, jejíž řešení jsou formální. Proto: ${\ Displaystyle ax+by = \ pm 1}$

${\ Displaystyle (m-1)^{m} \ cdot rm \ cdot s = -1}$, kde ${\ displaystyle s = 1+F}$

Protože a jsou relativně primární, existují celočíselná řešení podle Bézoutovy identity. Tuto rovnici lze přepsat jako: ${\ displaystyle m}$${\ Displaystyle m-1}$${\ displaystyle (r, s)}$

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

Ale ( m –1) ^m je polynom Z  · m –1, pokud m je lichý a Z  · m +1, je -li m sudý, kde Z je polynom s monomickým základem v m . Proto r ₀ = 1, pokud m je liché a r ₀ = –1, pokud m je sudé, je řešením.

Bézoutova identita poskytuje periodické řešení , takže nahrazení v diofantické rovnici a přeskupení: ${\ Displaystyle r = r_ {0}+k \ cdot m}$${\ displaystyle r}$

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

kde pro liché a pro i a je libovolné celé číslo. Pro danou hodnotu bude vybrán ten nejmenší klad, který splňuje omezení prohlášení o problému. ${\ displaystyle r_ {0} = 1}$${\ displaystyle m}$${\ displaystyle r_ {0} =-1}$${\ displaystyle m}$${\ displaystyle k}$${\ displaystyle m}$${\ displaystyle k}$${\ displaystyle N}$

Ve Williamově verzi problému je 5 námořníků, tedy 1, a může být považováno za nulu, aby byla získána nejnižší kladná odpověď, takže N = 1   · 5 ⁵ - 4 = 3121 pro počet kokosových ořechů v původní hromádce . (Lze poznamenat, že další postupné řešení rovnice pro k = –1 je –12504, takže pokus a omyl kolem nuly nevyřeší Williamsovu verzi problému, na rozdíl od původní verze, jejíž rovnice, naštěstí, měla negativní řešení malé velikosti). ${\ displaystyle m}$${\ displaystyle r_ {0}}$${\ displaystyle k}$

Zde je tabulka pozitivních řešení pro prvních pár ( je jakékoli nezáporné celé číslo): ${\ displaystyle N}$${\ displaystyle m}$${\ displaystyle k}$

${\ displaystyle m}$	${\ displaystyle N}$
2	${\ Displaystyle 11+k \ cdot 8}$
3	${\ Displaystyle 25+k \ cdot 81}$
4	${\ Displaystyle 765+k \ cdot 1024}$
5	${\ Displaystyle 3121+k \ cdot 15,625}$
6	${\ Displaystyle 233,275+k \ cdot 279,936}$
7	${\ Displaystyle 823,537+k \ cdot 5,764,801}$
8	${\ Displaystyle 117,440,505+k \ cdot 134,217,728}$

Další varianty a obecná řešení

Jiné varianty, včetně předpokládaného problému předchůdce, mají související obecná řešení pro libovolný počet námořníků.

Když má ranní rozdělení také zbývající část, řešení je:

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

For a to dává 15 621 jako nejmenší kladný počet kokosových ořechů pro před Williamovu verzi problému. ${\ displaystyle m = 5}$${\ displaystyle k = 1}$

V některých dřívějších alternativních formách problému vyšly divize rovnoměrně a matice (nebo položky) byly přiděleny ze zbývající hromady po rozdělení. V těchto formách je vztah rekurze:

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

Alternativní forma měla také dva konce, kdy vyšlo rovnoměrné ranní dělení a kdy opici zbyl jeden oříšek. Když vyjde ranní dělení, obecné řešení se redukuje podobným odvozením na:

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

Například když a , původní hromada má 1020 kokosových ořechů a po čtyřech po sobě jdoucích rovnoměrných děleních v noci s kokosem přiděleným opici po každé divizi zbývá ráno 80 kokosových ořechů, takže finální rozdělení vyjde dokonce bez zbytku kokosu. ${\ displaystyle m = 4}$${\ displaystyle k = 1}$

Když ranní rozdělení přinese oříšek, obecné řešení je:

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

kde if je liché a jestli je sudé. Například, když , a původní vlas má 51 kokosové ořechy a po třech po sobě jdoucích divize v noci s kokosem přidělené opice po každé divize, existuje 13 kokosové ořechy které zbyly v dopoledních hodinách, takže konečný divize má kokos zbylo po opici. ${\ displaystyle r_ {0} =-1}$${\ displaystyle m}$${\ displaystyle r_ {0} = 1}$${\ displaystyle m}$${\ displaystyle m = 3}$${\ displaystyle r_ {0} =-1}$${\ displaystyle k = 1}$

V literatuře byly zpracovány další post-Williamsovy varianty, které specifikují různé zbytky včetně pozitivních (tj. Opice přidává do hromady kokosové ořechy). Řešením je:

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

kde pro liché a pro i, je zbytek po každém oddělení (nebo počet opic) a je libovolné celé číslo ( je negativní, jestliže opice přidat kokosové ořechy na hromadu). ${\ displaystyle r_ {0} = 1}$${\ displaystyle m}$${\ displaystyle r_ {0} =-1}$${\ displaystyle m}$${\ displaystyle c}$${\ displaystyle k}$${\ displaystyle c}$

Jiné varianty, ve kterých se počet mužů nebo zbytků mezi jednotlivými divizemi liší, jsou obecně mimo třídu problémů spojených s opicí a kokosovými ořechy, ačkoli ty se podobně redukují na lineární diofantické rovnice ve dvou proměnných. Jejich řešení podléhají stejným technikám a nepředstavují žádné nové potíže.

Viz také

• Archimédův skotský problém , podstatně obtížnější diofantinský problém
• Fermatova poslední věta , možná nejslavnější diofantská rovnice ze všech
• Problém s dělovou koulí

Reference

Prameny

• Antonick, Gary (2013). Opice a kokosové ořechy Martina Gardnera v Numberplay The New York Times : 7. října 2013
• Pleacher, David (2005). Problém týdne: Opice a kokosy 16. května 2005
• Gardner, Martin (2001). The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems WW Norton & Company; ISBN  0-393-02023-1
• Pappas, Theoni (1993). Joy of Mathematics: Objevování matematiky všude kolem Wide World Publishing, 23. ledna 1993, ISBN  0933174659
• Wolfram Mathworld: Opičí a kokosový problém
• Kirchner, RB „Obecný problém s kokosem“. Amer. Matematika. Měsíčně 67, 516-519, 1960.
• Fadiman, Clifton (1962). Matematická straka , Simon & Schuster
• Bogomolny, Alexander (1996) Negativní kokosové ořechy na hranici uzlu

externí odkazy

• Opice a kokosové ořechy - video Numberphile
• Kokosové ořechy , kopie příběhu, jak se objevil v sobotním večerním příspěvku