Małpa i kokosy

Najmniejsze pozytywne rozwiązania zagadki małpy i orzechów kokosowych z sześciennymi kokosami

Oryginalna wersja z jednym kokosem

Wersja Williamsa, bez resztek kokosów

Małpa i orzechy kokosowe to matematyczna łamigłówka z dziedziny analizy diofantycznej , która wywodzi się z fikcyjnego opowiadania magazynu o pięciu marynarzach i małpie na bezludnej wyspie, którzy dzielą stos kokosów ; problem polega na znalezieniu liczby kokosów w oryginalnym stosie (niedozwolone są ułamkowe orzechy kokosowe). Problem jest znany ze swojej kłopotliwej trudności dla nieskomplikowanych osób rozwiązujących łamigłówki, chociaż przy odpowiednim podejściu matematycznym rozwiązanie jest trywialne. Problem stał się podstawą matematyki rekreacyjnej kolekcje.

Ogólny opis

Problem można wyrazić jako:

Jest tam stos kokosów, należący do pięciu mężczyzn. Jeden mężczyzna dzieli stos na pięć równych stosów, ten, który został z kokosa, przekazuje przechodzącej małpie i zabiera swoją część. Następnie drugi mężczyzna powtarza procedurę, dzieląc pozostały stos na pięć i zabierając swoją część, podobnie jak trzeci, czwarty i piąty, każdy z nich znajduje po jednym kokosie pozostałym po podzieleniu stosu przez pięć i przekazuje go małpa. Na koniec grupa dzieli pozostałe orzechy kokosowe na pięć równych stosów: tym razem żaden kokos nie zostaje.

Ile kokosów było w oryginalnym stosie?

Małpa i orzechy kokosowe to najbardziej znany przedstawiciel klasy problemów łamigłówek wymagających rozwiązań całkowitoliczbowych zorganizowanych jako rekurencyjne dzielenie lub frakcjonowanie pewnej dyskretnie podzielnej wielkości, z resztami lub bez, oraz końcowy podział na pewną liczbę równych części, prawdopodobnie z reszta. Problem jest tak dobrze znany, że cała klasa jest często określana ogólnie jako „problemy typu małpy i kokosa”, chociaż większość z nich nie jest ściśle związana z problemem.

Inny przykład: „Mam całą liczbę funtów cementu, nie wiem ile, ale po dodaniu dziewiątej i jedenastej podzielono to na 3 worki, każdy po pełnej liczbie funtów. Ile funtów cementu miałem?”

Problemy proszą o początkową lub końcową ilość. Podana lub dorozumiana to najmniejsza liczba dodatnia, która może być rozwiązaniem. W takich zadaniach są dwie niewiadome, liczba początkowa i liczba końcowa, ale tylko jedno równanie, które jest algebraiczną redukcją wyrażenia dla relacji między nimi. Wspólny dla tej klasy jest charakter otrzymanego równania, które jest liniowym równaniem diofantycznym z dwiema niewiadomymi. Większość członków tej klasy jest zdeterminowana, ale niektórzy nie (małpa i orzechy kokosowe należą do tych ostatnich). Znane algebraiczne nie nadają się do rozwiązywania takich równań.

Historia

Pochodzenie klasy takich problemów zostało przypisane indyjskiemu matematykowi Mahāvīrze w rozdziale VI, § 131 1 ⁄ 2 , 132 1 ⁄ 2 jego Ganita-sara-sangraha („Kompendium esencji matematyki”), około 850 roku n.e. , który zajmował się seryjnym podziałem owoców i kwiatów z określonymi resztami. To sprawiłoby, że progenitorowe problemy miały ponad 1000 lat przed ich odrodzeniem w epoce nowożytnej. Problemy z dzieleniem, które odwołują się do chińskiego twierdzenia o resztach pojawił się w literaturze chińskiej już w I wieku n.e. Sun Tzu zapytał: Znajdź liczbę, która daje resztę 2, 3 i 2 przy dzieleniu odpowiednio przez 3, 5 i 7. Diofant z Aleksandrii po raz pierwszy badał problemy wymagające rozwiązań całkowitoliczbowych w III wieku n.e. Algorytm Euklidesa dla największego wspólnego dzielnika, który leży u podstaw rozwiązywania takich problemów, został odkryty przez greckiego geometrę Euklidesa i opublikowany w jego Elementach w 300 roku n.e.

Profesor David Singmaster , historyk zagadek, śledzi serię mniej wiarygodnie powiązanych problemów w średniowieczu, z kilkoma odniesieniami aż do czasów imperium babilońskiego około 1700 roku pne. Obejmują ogólny temat dodawania lub odejmowania ułamków stosu lub określonej liczby dyskretnych obiektów i pytania, ile mogło ich być na początku. Następne odniesienie do podobnego problemu znajduje się w Récréations mathématiques et physiques Jacquesa Ozanama , 1725. W dziedzinie czystej matematyki Lagrange w 1770 wyjaśnił swoje twierdzenie o ułamkach ciągłych i zastosował ją do rozwiązywania równań diofantycznych.

Pierwszy opis problemu, zbliżony do jego współczesnego sformułowania, pojawił się w pamiętnikach matematyka i autora Lewisa Carrolla („Alicja w krainie czarów”) w 1888 roku, dotyczący stosu orzechów na stole podzielonym kolejno przez czterech braci, za każdym razem z reszta z jednego dana małpie, a ostateczny podział wychodzi równy. Problem nigdy nie pojawił się w żadnej z opublikowanych prac autora, chociaż z innych źródeł wydaje się, że problem ten był w obiegu w 1888 roku. Niemal identyczny problem pojawił się wkrótce w Elementary Algebra WW Rouse Balla , 1890. Taka bliskość sugeruje wspólne źródło; rozpowszechnienie problemu mogło nastąpić poprzez wymianę zdań Carrolla z Bartholomew Price , profesorem matematyki oraz przyjacielem i nauczycielem Carrol. Istniały cztery wersje problemu: dwie formy, jedna z resztami z jednego i druga z resztami z zera, ale orzechami odrzuconymi po dzieleniu, oraz dwa zakończenia, jedno, w którym końcowe dzielenie ma resztę, a drugie, w którym wychodzi parzyste (lub bez orzechów są odrzucane). Problem był wspominany w pracach matematyków z epoki, z rozwiązaniami, w większości błędnymi, co wskazywało, że problem był nowy i nieznany w tamtym czasie.

Urządzenie z zaznaczonymi przedmiotami (patrz Niebieskie orzechy kokosowe poniżej), aby pomóc w konceptualizacji podziału z pozostałościami, pojawiło się po raz pierwszy w 1912 r. W pracy Normana H. Anninga, dotyczącej pojemnika z jabłkami podzielonego przez trzech mężczyzn.

Problem stał się głośny, gdy amerykański powieściopisarz i autor opowiadań Ben Ames Williams zmodyfikował starszy problem i umieścił go w opowiadaniu „Kokosy” w numerze Saturday Evening Post z 9 października 1926 roku . Oto jak problem został stwierdzony przez Williamsa (skondensowany i sparafrazowany):

Pięciu ludzi i małpa rozbili się na wyspie. Pierwszy dzień spędzili na zbieraniu kokosów. W nocy obudził się jeden mężczyzna i postanowił wziąć swoją część kokosów. Podzielił je na pięć stosów. Został jeden kokos, więc dał go małpie, potem schował swoją część, resztę złożył z powrotem i ponownie zasnął.

Wkrótce drugi mężczyzna obudził się i zrobił to samo. Po podzieleniu kokosów na pięć stosów został jeden kokos, który dał małpie. Następnie ukrył swój udział, złożył resztę z powrotem i wrócił do łóżka. Trzeci, czwarty i piąty mężczyzna postępowali dokładnie w ten sam sposób. Następnego ranka, gdy wszyscy się obudzili, podzielili pozostałe orzechy kokosowe na pięć równych części. Tym razem nie zostały żadne kokosy.

Ile kokosów było w oryginalnym stosie?

Williams nie zawarł odpowiedzi w historii. Czasopismo zostało zalane ponad 2000 listami błagającymi o rozwiązanie problemu. Redaktor postu, Horace Lorimer , wysłał słynny telegram do Williamsa, mówiąc: „NA MIŁOŚĆ DO MIKE'A, ILE KOKOSÓW? Williams nadal otrzymywał listy z prośbą o rozwiązanie lub proponowanie nowych na następne dwadzieścia lat.

Martin Gardner przedstawił ten problem w swojej kolumnie Mathematical Games z kwietnia 1958 r. w Scientific American . Stwierdził, że Williams zmodyfikował starszy problem, aby był bardziej zagmatwany. W starszej wersji na ostatnim podziale jest kokos dla małpy; w wersji Williamsa finałowy podział rano wychodzi na zero. Jednak dostępne dowody historyczne nie wskazują, do których wersji Williams miał dostęp. Gardner powiedział kiedyś swojemu synowi Jimowi, że jest to jego ulubiony problem do tego stopnia, że później postanowił uczynić z niego pierwszy rozdział swojej kolekcji „najlepszych z felietonów”, Kolosalna księga matematyki . Powiedział, że Małpa i orzechy kokosowe to „prawdopodobnie najczęściej opracowywana i najrzadziej rozwiązywana” łamigłówka diofantyczna. Od tego czasu wersja problemu Williamsa stała się podstawą matematyki rekreacyjnej . Oryginalna historia zawierająca problem została przedrukowana w całości w antologii Cliftona Fadimana The Mathematical Magpie z 1962 r ., książce, którą Mathematical Association of America zaleca do nabycia przez biblioteki matematyczne dla studentów studiów licencjackich.

W literaturze pojawiło się wiele wariantów różniących się liczbą marynarzy, małp czy kokosów.

Rozwiązania

Problem diofantyczny

Analiza diofantyczna to badanie równań o wymiernych współczynnikach wymagających rozwiązań całkowitych. W problemach diofantycznych jest mniej równań niż niewiadomych. „Dodatkową” informacją wymaganą do rozwiązania równań jest warunek, aby rozwiązania były liczbami całkowitymi. Każde rozwiązanie musi spełniać wszystkie równania. Niektóre równania diofantyczne nie mają rozwiązania, niektóre mają jedno lub skończoną liczbę, a jeszcze inne mają nieskończenie wiele rozwiązań.

Małpa i orzechy kokosowe redukują się algebraicznie do liniowego równania diofantycznego z dwiema zmiennymi postaci

ax + by = c lub bardziej ogólnie

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

gdzie d jest największym wspólnym dzielnikiem a i b . Dzięki tożsamości Bézouta równanie jest rozwiązywalne wtedy i tylko wtedy, gdy d dzieli c . Jeśli tak, równanie ma nieskończenie wiele okresowych rozwiązań postaci

₀ x = x + t · b ,

₀ y = y + t · za

gdzie ( x ₀ , y ₀ ) jest rozwiązaniem, a t jest parametrem, niż może być dowolną liczbą całkowitą. Problem nie ma być rozwiązany metodą prób i błędów; istnieją deterministyczne metody rozwiązywania ( x ₀ , y ₀ ) w tym przypadku (patrz tekst).

Już od 1928 roku opublikowano wiele rozwiązań zarówno pierwotnego problemu, jak i modyfikacji Williamsa. Sprytne i zwięzłe rozwiązania wykorzystujące kongruencje modulo, sita i alternatywne podstawy liczb zostały opracowane w oparciu częściowo lub w większości o rekurencyjną definicję problemu, strukturę, która nie będzie miała zastosowania w ogólnym przypadku. Najmniejsze pozytywne rozwiązania dla obu wersji są na tyle duże, że metoda prób i błędów najprawdopodobniej będzie bezowocna. Wprowadzono pomysłową koncepcję negatywnych orzechów kokosowych, która szczęśliwie rozwiązuje pierwotny problem. Rozwiązania formalistyczne oparte są na algorytmie Euklidesa zastosowanym do współczynników diofantycznych. Wreszcie, rachunek różnic skończonych daje sparametryzowane rozwiązanie ogólne dla dowolnej liczby marynarzy i wszystkich wielokrotności orzechów kokosowych, które mogły znajdować się na pierwotnym stosie. W dzisiejszych czasach komputerowe przeszukiwanie dodatnich liczb całkowitych szybko daje rozwiązanie.

Przed przystąpieniem do rozwiązania problemu można zauważyć kilka rzeczy. Gdyby nie było reszty, biorąc pod uwagę, że istnieje 6 podziałów po 5, 5 ⁶ = 15 625 orzechów kokosowych musi znajdować się w stosie; w 6. i ostatniej dywizji każdy marynarz otrzymuje 1024 kokosy. Żadna mniejsza liczba dodatnia nie spowoduje, że wszystkie 6 dywizji wypadnie parzyście. Oznacza to, że w podanym problemie do stosu można dodać dowolną wielokrotność 15 625, co spełni warunki problemu. Oznacza to również, że liczba orzechów kokosowych w oryginalnym stosie jest mniejsza niż 15 625, w przeciwnym razie odjęcie 15 625 da mniejsze rozwiązanie. Ale liczba w oryginalnym stosie nie jest trywialnie mała, jak 5 lub 10 (dlatego jest to trudny problem) – może to być w setkach lub tysiącach. W przeciwieństwie do prób i błędów w przypadku odgadywania pierwiastka wielomianu, próba i błąd w przypadku pierwiastka diofantycznego nie doprowadzi do żadnej oczywistej zbieżności. Nie ma prostego sposobu oszacowania, jakie będzie rozwiązanie.

Oryginalna wersja

Podsumowanie analizy zarówno pierwotnego problemu, jak i wersji Williamsa zostało przedstawione przez Martina Gardnera , kiedy opisał problem w swojej kolumnie Gry matematyczne. Gardner zaczyna od rozwiązania pierwotnego problemu, ponieważ jest mniej kłopotliwy niż wariant Williamsa. Niech N będzie wielkością pierwotnego stosu, a F liczbą kokosów otrzymanych przez każdego marynarza po ostatecznym podziale na 5 równych części rano. Wtedy liczba kokosów pozostałych przed porannym podziałem wynosi F · 5+1. Jeśli ta ilość jest oznaczona jako n , liczba pozostająca przed dywizją ostatniego marynarza to:

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

odwrócenie postępowania marynarza w nocy. Ale każdy marynarz postępował zgodnie z tą samą procedurą; w ten sposób zdefiniowano rekurencyjną serię 5 takich s (zastępując $n}$ $displaystyle$ przez ${\ displaystyle n'}$ i generując nowy ${\ displaystyle n'}$ ), n ′ piątym i ostatnim z nich jest samo N , liczba orzechów kokosowych przed podziałem przez pierwszego żeglarza. Kolejno podstawiając ${\ displaystyle n'}$ s i ${\ displaystyle n}$ daje:

{\ 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 sprowadza się do równania diofantycznego:

{\ Displaystyle 1024N = 15625F + 11529}

Z podstawowego twierdzenia wynika, że to równanie ma rozwiązanie wtedy i tylko wtedy, gdy 11529 jest wielokrotnością największego wspólnego dzielnika liczb 1024 i 15625. 1024=4 ⁵ i 15625=5 ⁶ , więc ich NWD wynosi 1, a 11529 jest wielokrotnością 1, więc równanie jest rozwiązywalne.

Gardner zwraca uwagę, że to równanie jest zbyt trudne do rozwiązania metodą prób i błędów. Co więcej, ma nieskończoną liczbę rozwiązań. Ale Gardner mylił się co do trudności. W rzeczywistości, jeśli (N, F) jest rozwiązaniem, to jest nim również (N + 15625 t, F + 1024 t) dla dowolnej liczby całkowitej t . Oznacza to, że równanie ma również rozwiązania w ujemnych liczbach całkowitych. Wypróbowując kilka małych liczb ujemnych okazuje się, że N = -4 i F = -1 to rozwiązanie. Wiąże się to z absurdalnym pojęciem negatywnych orzechów kokosowych; więc dodajemy 15625 do -4 i dodajemy 1024 do -1, aby otrzymać najmniejsze pozytywne rozwiązanie (15621, 1023) .

Wersja Williamsa

Negatywne podejście do kokosów nie ma zastosowania do wersji Williamsa, przynajmniej nie dla jakichkolwiek rozsądnie małych | N |, więc potrzebne jest bardziej systematyczne podejście.

Za pomocą sita

Przestrzeń poszukiwań można zmniejszyć o szereg coraz większych czynników, obserwując strukturę problemu, tak aby odrobina prób i błędów znalazła rozwiązanie. Przestrzeń poszukiwań jest znacznie mniejsza, jeśli zacznie się od liczby kokosów otrzymanych przez każdego mężczyznę w porannym podziale, ponieważ liczba ta jest znacznie mniejsza niż liczba w pierwotnym stosie.

Jeśli F to liczba kokosów, które każdy żeglarz otrzymuje rano w końcowym podziale, poranny stos wynosi 5 F , co również musi być podzielne przez 4, ponieważ ostatni żeglarz w nocy połączył 4 stosy w porannym podziale. Zatem poranny stos, nazwijmy go liczbą n , jest wielokrotnością 20. Stos przed przebudzeniem ostatniego marynarza musiał wynosić 5/4( n )+1. Jeśli tylko jeden marynarz obudził się w nocy, to 5/4(20)+1 = 26 działa dla minimalnej liczby kokosów w pierwotnym stosie. Ale jeśli obudziło się dwóch marynarzy, 26 nie jest podzielne przez 4, więc poranny stos musi być jakąś wielokrotnością 20, która daje stos podzielny przez 4, zanim ostatni marynarz się obudzi. Tak się składa, że 3*20=60 działa dla dwóch żeglarzy: stosując wzór rekurencji dla n dwukrotnie daje 96 jako najmniejszą liczbę orzechów kokosowych w oryginalnym stosie. 96 jest ponownie podzielne przez 4, więc dla przebudzenia 3 żeglarzy stos mógł wynosić 121 kokosów. Ale 121 nie jest podzielne przez 4, więc dla przebudzenia 4 marynarzy trzeba zrobić kolejny skok. W tym momencie analogia staje się niejasna, ponieważ aby pomieścić 4 budzących się marynarzy, poranny stos musi być jakąś wielokrotnością 60: jeśli ktoś jest wytrwały, może się okazać, że 17*60=1020 załatwia sprawę i minimalna liczba w oryginalnym stosie byłoby 2496. Ostatnia iteracja 2496 dla przebudzenia 5 marynarzy, tj. 5/4(2496)+1, podnosi oryginalny stos do 3121 kokosów.

Niebieskie kokosy

Innym urządzeniem poprzedzającym problem jest użycie dodatkowych lub oznaczonych obiektów, w tym przypadku niebieskich orzechów kokosowych, w celu wyjaśnienia procesu podziału. Załóżmy, że pierwszy marynarz przed dzieleniem dodaje do stosu cztery niebieskie kokosy, aby zagwarantować dzielenie przez 5 (ponieważ wiemy, że nawet jeśli tego nie zrobi, zostanie reszta z 1, więc dodanie 4 sprawia, że stos jest podzielny przez 5). Dzieli stos, bierze piąty z dodatkowym (nieniebieskim) kokosem, który rzuca małpie, chowa swoją część, a następnie układa resztę z powrotem, odkładając 4 niebieskie kokosy na bok. Każdy marynarz robi to samo. Po piątym marynarzu (lub po podziale rano, jeśli jest tam reszta), niebieskie kokosy zostają na boku, nie należą do nikogo. Ponieważ oryginalny stos jest podzielony 5 razy (lub 6, jeśli rano jest reszta), wliczając w to niebieskie kokosy, musiało to być 5 ⁵ (5 ⁶ ) orzechów kokosowych. To daje stos 3125-4=3121 (15625-4=15621) kokosów. Niebieskie kokosy można uznać za „wirtualne” kokosy, które nie odgrywają żadnej roli w problemie, służą jedynie wyjaśnieniu podzielności.

Numeracja bazowa 5

₀₀ Proste i oczywiste rozwiązanie pojawia się, gdy wykonujemy dzielenie i odejmowanie w podstawie 5. Rozważmy odejmowanie, gdy pierwszy marynarz bierze swoją część (i małpę). Niech n ,n ₁ ,... reprezentują cyfry N, liczbę kokosów w oryginalnym stosie, a s ,s ₁ ... reprezentują cyfry udziału marynarza S, obie o podstawie 5. Po udziale małpy, najmniej znacząca cyfra N musi teraz wynosić 0; po odjęciu najmniej znaczącą cyfrą N' pozostawioną przez pierwszego żeglarza musi być 1, stąd (rzeczywista liczba cyfr w N i S jest nieznana, ale w tej chwili są one nieistotne):

₀ n ₅ n ₄ n ₃ n ₂ n ₁ 0 (N ₅ ) s ₄ s ₃ s ₂ s ₁ s  (S ₅ ) 1 (N' ₅ )

₀₀ Cyfra odjęta od 0 o podstawie 5 dająca 1 wynosi 4, więc s = 4. Ale ponieważ S to (N-1)/5, a dzielenie przez 5 ₅ to po prostu przesunięcie liczby o jedną pozycję w prawo, n ₁ = s = 4. Teraz odejmowanie wygląda następująco:

 n ₅ n ₄ n ₃ n ₂ 4 0 sek ₄ sek ₃ sek ₂ sek ₁ 4 1

Ponieważ następny żeglarz zamierza zrobić to samo na N', najmniej znacząca cyfra N' staje się 0 po rzuceniu jednej małpie, a LSD S' musi wynosić 4 z tego samego powodu; następną cyfrą N' też musi być 4. Teraz wygląda to tak:

 n ₅ n ₄ n ₃ n ₂ 4 0 sek ₄ sek ₃ sek ₂ sek ₁ 4 4 1

Pożyczenie 1 z n ₁ (które teraz wynosi 4) pozostawia 3, więc s ₁ musi wynosić 4, a zatem n ₂ również. Więc teraz wygląda to tak:

 n ₅ n ₄ n ₃ 4 4 0 sek ₄ sek ₃ sek ₂ 4 4 4 1

Ale to samo rozumowanie ponownie odnosi się do N', tak jak do N, więc następna cyfra N' to 4, więc s ₂ i n ₃ to także 4 itd. Istnieje 5 podziałów; pierwsza czwórka musi zostawić nieparzystą podstawę 5 w stosie do następnego podziału, ale ostatnia dywizja musi zostawić parzystą podstawę 5, aby poranny podział wyszedł parzyście (za 5 s). Więc są cztery czwórki w N następujące po LSD równym 1: N=44441 ₅ = 3121 ₁₀

Podejście numeryczne

Prosta analiza numeryczna wygląda następująco: jeśli N jest liczbą początkową, każdy z 5 żeglarzy przenosi oryginalny stos w następujący sposób:

N => 4(N–1)/5 lub równoważnie N => 4(N+4)/5 – 4.

Powtórzenie tego przejścia 5 razy daje liczbę pozostałą rano:

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

Ponieważ ta liczba musi być liczbą całkowitą, a 1024 jest względnie pierwszą liczbą 3125, N+4 musi być wielokrotnością 3125. Najmniejsza taka wielokrotność to 3125 · 1, więc N = 3125 – 4 = 3121; liczba pozostawiona rano dochodzi do 1020, co jest równo podzielne przez 5, zgodnie z wymaganiami.

Kongruencja modulo

Proste, zwięzłe rozwiązanie można uzyskać, bezpośrednio wykorzystując rekurencyjną strukturę problemu: orzechów kokosowych podzielono na piąte części, za każdym razem pozostawiając jedną (pomijając ostatni podział rano). Stos pozostały po każdym podziale musi zawierać całkowitą liczbę orzechów kokosowych. Gdyby istniał tylko jeden taki podział, to od razu widać, że rozwiązaniem jest 5 · 1+1=6. W rzeczywistości każda wielokrotność pięciu plus jeden jest rozwiązaniem, więc możliwy ogólny wzór to 5 · k – 4, ponieważ wielokrotność 5 plus 1 jest również wielokrotnością 5 minus 4. Zatem 11, 16 itd. również działają dla jednego dział.

zamiast 5 należy użyć wielokrotności 5 · 5=25, ponieważ 25 można podzielić przez 5 dwukrotnie. Zatem liczba orzechów kokosowych, które mogą znajdować się w stosie, wynosi k · 25 – 4. k = 1 dające 21 to najmniejsza liczba dodatnia, którą można kolejno podzielić dwukrotnie przez 5 z resztą 1. Jeśli jest 5 podziałów, to wielokrotności 5 ⁵ = 3125 są wymagane; najmniejsza taka liczba to 3125 – 4 = 3121. Po 5 podziałach zostaje 1020 kokosów, czyli liczba podzielna przez 5 zgodnie z wymaganiami zadania. Właściwie po n podziałów, można udowodnić, że pozostały stos jest podzielny przez n , właściwość wygodnie wykorzystana przez twórcę problemu.

Formalny sposób sformułowania powyższego argumentu to:

Pierwotny stos kokosów zostanie podzielony przez 5 w sumie 5 razy z resztą 1, nie biorąc pod uwagę ostatniego podziału rano. Niech N = liczba kokosów w pierwotnym stosie. Każda dywizja musi pozostawić liczbę orzechów w tej samej klasie kongruencji (mod 5). Więc,

{\ Displaystyle N \ równoważnik 4/5 \ cdot (N-1)}

(mod 5) (-1 to orzech rzucony małpie)

{\ Displaystyle 5N \ równoważnik 4N-4}

(mod 5)

{\ Displaystyle N \ równoważnik -4}

(mod 5) (–4 to klasa kongruencji)

Jeśli więc zaczynaliśmy w klasie modulo –4 nakrętki, to pozostaniemy w klasie modulo –4. Ponieważ ostatecznie musimy podzielić stos 5 razy lub 5^5, pierwotny stos wynosił 5^5 – 4 = 3121 kokosów. Pozostała część 1020 orzechów kokosowych wygodnie dzieli się równo o 5 rano. To rozwiązanie zasadniczo odwraca sposób, w jaki problem został (prawdopodobnie) skonstruowany.

Równanie diofantyczne i formy rozwiązań

Równoważne równanie diofantyny dla tej wersji to:

{\ Displaystyle 1024N = 15625F + 8404}

(1)

gdzie N to pierwotna liczba orzechów kokosowych, a F to liczba otrzymana przez każdego żeglarza na ostatnim podziale rano. Jest to tylko nieznacznie różne od powyższego równania dla poprzedniego problemu, a rozwiązanie jest gwarantowane przez to samo rozumowanie.

zmiana kolejności,

{\ Displaystyle 1024N-15625F = 8404}

(2)

₀₀₀₀ ₀₀ To równanie diofantyczne ma rozwiązanie, które wynika bezpośrednio z algorytmu euklidesowego ; w rzeczywistości ma nieskończenie wiele okresowych rozwiązań dodatnich i ujemnych. Jeśli (x , y ) jest rozwiązaniem 1024x–15625y=1, to N =x · 8404, F =y · 8404 jest rozwiązaniem (2), co oznacza, że każde rozwiązanie musi mieć postać

{\ Displaystyle {\ rozpocząć {przypadki} N = N_ {0} + 15625 \ cdot t \\ F = F_ {0} + 1024 \ cdot t \ koniec {przypadki}}}

(3)

gdzie $dowolnym$ parametrem, który może mieć dowolną wartość całkowitą.

Podejście redukcjonistyczne

Można wziąć obie strony (1) powyżej modulo 1024, więc

{\ Displaystyle 1024N = 15625F + 8404 \ mod 1024}

Innym sposobem myślenia o tym jest to, że aby być $całkowitą$ , RHS równania musi być całkowitą wielokrotnością 1024; ta właściwość pozostanie niezmieniona po odrzuceniu jak największej liczby wielokrotności 1024 z RHS. Zmniejszając obie strony o wielokrotności 1024,

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

odejmowanie,

{\ Displaystyle 0 = 265F + 212 \ mod 1024}

faktoring,

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

RHS nadal musi być wielokrotnością 1024; ponieważ 53 jest względnie pierwszą liczbą 1024, 5 F +4 musi być wielokrotnością 1024. Najmniejsza taka wielokrotność to 1 · 1024, więc 5 F +4 = 1024 i F = 204. Podstawiając do (1)

{\ Displaystyle 1024N = 15625 \ cdot 204 + 8404 \ Strzałka w prawo N = {\ Frac {3195904} {1024}} \ Strzałka w prawo N = 31 21}

Algorytm euklidesowy

Algorytm Euklidesa jest dość żmudny, ale jest ogólną metodologią rozwiązywania równań wymiernych ax+by=c wymagającą odpowiedzi całkowitych. Z powyższego (2) widać, że 1024 (2 ¹⁰ ) i 15625 (5 ⁶ ) są względnie pierwsze, a zatem ich NWD wynosi 1, ale potrzebujemy równań redukcji dla podstawienia wstecznego, aby otrzymać N i F w kategoriach tych dwóch wielkie ilości:

Najpierw uzyskaj kolejne reszty, aż pozostanie NWD:

15625 = 15·1024 + 265 (a)

1024 = 3·265 + 229 (b)

265 = 1·229 + 36 (c)

229 = 6·36 + 13 (re)

36 = 2·13 + 10 (e)

13 = 1·10 + 3 (f)

10 = 3·3 + 1 (g) (reszta 1 to NWD 15625 i 1024)

1 = 10 – 3(13–1·10) = 4·10 – 3·13 (zmień kolejność (g), zastąp 3 z (f) i połącz)

1 = 4·(36 – 2·13) – 3·13 = 4·36 – 11·13 (zastąp 10 z (e) i połącz)

1 = 4·36 – 11·(229 – 6·36) = –11·229 + 70*36 (zastąp 13 z (d) i połącz)

1 = –11·229 + 70·(265 – 1·229) = –81·229 + 70·265 (zastąp 36 z (c) i połącz)

1 = –81·(1024 – 3·265) + 70·265 = –81·1024 + 313·265 (zastąp 229 z (b) i połącz)

1 = –81·1024 + 313·(15625 – 15·1024) = 313·15625 – 4776·1024 (zastąp 265 z (a) i połącz)

₀₀ Zatem para (N ,F ) = (-4776·8404, -313*8404); najmniejsza (patrz (3) w poprzednim podrozdziale), która sprawi, że zarówno N, jak i F będą dodatnie, to 2569, więc: ${\ displaystyle t}$

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

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

Ciąg dalszy ułamka

₀₀ Alternatywnie można użyć ułamka ciągłego, którego konstrukcja oparta jest na algorytmie euklidesowym. Ułamek ciągły dla 1024 ⁄ 15625 (dokładnie 0,065536) wynosi [;15,3,1,6,2,1,3 ] ; jego zbieżność zakończona po powtórzeniu wynosi 313 / 4776 , co daje nam x = –4776 i y =313. Najmniejsza wartość t , dla której zarówno N, jak i F są nieujemne, to 2569, więc

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

.

Jest to najmniejsza liczba dodatnia, która spełnia warunki zadania.

Uogólnione rozwiązanie

Kiedy liczba marynarzy jest parametrem, niech będzie to $obliczeniowa$ , ostrożna algebraiczna redukcja relacji między liczbą kokosów w pierwotnym stosie a liczbą przydzieloną każdemu marynarzowi rano m {\ displaystyle m} daje analogiczną relację diofantyczną, której współczynniki są wyrażeniami w ${\ displaystyle m}$ .

Pierwszym krokiem jest uzyskanie algebraicznego rozwinięcia relacji powtarzalności odpowiadającej transformacji stosu przez każdego marynarza, przy czym liczba pozostawiona przez marynarza jest liczbą: ${\ displaystyle n_ {i}}$

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

gdzie ${\ Displaystyle n_ {i \ rightarrow 0} \ równoważnik N}$ , liczba pierwotnie $liczba$ . Rozszerzenie nawrotu przez zastąpienie n $\ displaystyle n_ {i}}$ razy daje: ${\ displaystyle n_ {i-1}}$ ${\ displaystyle m}$

{\ Displaystyle n_ {m} = \ lewo ({\ Frac {m-1} {m}} \ prawej) ^ {m} \ cdot n_ {0} -\lewo[({\frac {m-1}{m}})^{m}+...+({\frac {m-1}{m}})^{2}+{\frac { m-1}{m}}\prawo]}

Uwzględniając ten ostatni termin,

{\ Displaystyle n_ {m} = \ lewo ({\ Frac {m-1} {m}} \ prawo) ^ {m} \ cdot n_ {0} - \ lewo ({\ Frac {m-1} {m }}\right)\cdot \left[({\frac {m-1}{m}})^{m-1}+...+{\frac {m-1}{m}}+1\ Prawidłowy]}

Wielomian szeregu potęgowego w nawiasach postaci ${\ Displaystyle x ^ {m-1} +... + x + 1}$ sumuje się do ${\ Displaystyle (1-x ^ {m}) / (1-x)}$ więc,

{\ Displaystyle n_ {m} = \ lewo ({\ Frac {m-1} {m}} \ prawo) ^ {m} \ cdot n_ {0} - \ lewo ({\ Frac {m-1} {m }}\right)\cdot \left[\left(1-({\frac {m-1}{m}})^{m}\right){\bigg /}\left(1-({\frac {m-1}{m}})\prawo)\prawo]}

co upraszcza do:

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

Ale $m$ liczba pozostawiona rano, która jest wielokrotnością (tj . liczba przydzielona każdemu marynarzowi rano): $}$ $m$

{\ Displaystyle m \ cdot F = \ lewo ({\ Frac {m-1} {m}}\right)^{m}\cdot n_{0}-(m-1)\cdot {\frac {m^{m}-(m-1)^{m}}{m^{m }}}}

Rozwiązywanie dla (= ${\ displaystyle N}$ ), n { $displaystyle n_ {0}}$

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

Równanie jest liniowym równaniem diofantycznym $.$ dwóch $zmiennych$ i ${\ displaystyle m}$ jest parametrem, który może być dowolną liczbą całkowitą. Charakter równania i metoda jego rozwiązania nie zależą od ${\ displaystyle m}$ .

Obowiązują teraz rozważania z zakresu teorii liczb. Aby $całkowitą$ , wystarczy, że ${\ Displaystyle {\ Frac {m-1 + m \ cdot F} {(m-1 ) ^ {m}}}}$ będzie liczbą całkowitą, więc niech będzie ${\ displaystyle r}$ :

{\ Displaystyle R = {\ Frac {m-1 + m \ cdot F} {(m-1) ^ {m}}}}

Równanie $do$ przekształcić Stąd:

{\ Displaystyle (m-1) ^ {m} \ cdot rm \ cdot s = -1}

, gdzie

{\ Displaystyle s = 1 +F}

Ponieważ i $displaystyle (r, s)} .$ $s$ , istnieją rozwiązania całkowite według Bézouta ${$ To równanie można przekształcić jako:

{\ Displaystyle (m-1) ^ {m} \ cdot r \ równoważnik -1 \ mod m}

Ale ( m –1) ^m jest wielomianem Z · m –1, jeśli m jest nieparzyste i Z · m +1, jeśli m jest parzyste, gdzie Z jest wielomianem o jednomianowej podstawie w m . Dlatego r ₀ = 1, jeśli m jest nieparzyste, a r ₀ = –1, jeśli m jest parzyste, jest rozwiązaniem.

Tożsamość Bézouta daje rozwiązanie okresowe , więc zastępując w równaniu diofantycznym i przestawiając: $= r_ {0} + k \ cdot m}$ $displaystyle$

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

gdzie ${\ Displaystyle r_ {0} = 1}$ dla nieparzystych i $r_ {0} = -1}$ $Displaystyle$ m $\ Displaystyle m}$ parzystych i ${\ displaystyle k}$ jest dowolną liczbą całkowitą. Dla danego $spełnia$ dodatniego zostanie wybrany taki, $że$ $problemu$ .

W wersji problemu Williama $\$ 5 marynarzy, więc $1$ , a można przyjąć, że wynosi zero, aby uzyskać najniższą pozytywną odpowiedź m $displaystyle m}$ , więc N = 1 · 5 ⁵ – 4 = 3121 dla liczby kokosów w pierwotnym stosie. (Można zauważyć, że następne kolejne rozwiązanie równania dla k =–1, wynosi –12504, więc metoda prób i błędów wokół zera nie rozwiąże problemu w wersji Williamsa, w przeciwieństwie do wersji oryginalnej, której równanie na szczęście miało rozwiązanie ujemne o małej wielkości).

Oto tabela pozytywnych rozwiązań dla pierwszych kilku $displaystyle$ k $\$ $k}$ jest dowolną nieujemną liczbą całkowitą): N {\ displaystyle N

${\ 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 15625}$
6	${\ Displaystyle 233275 + k \ cdot 279936}$
7	${\ Displaystyle 823537 + k \ cdot 5764801}$
8	${\ Displaystyle 117 440 505 + k \ cdot 134 217 728}$

Inne warianty i rozwiązania ogólne

Inne warianty, w tym domniemany problem poprzednika, mają powiązane ogólne rozwiązania dla dowolnej liczby marynarzy.

Gdy poranny podział ma również resztę jedynki, rozwiązaniem jest:

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

Dla ${\ displaystyle m = 5}$ i ${\ displaystyle k = 1}$ daje to 15 621 jako najmniejszą dodatnią liczbę orzechów kokosowych dla wersji problemu sprzed Williama.

W niektórych wcześniejszych alternatywnych formach problemu podziały były równe, a orzechy (lub przedmioty) były przydzielane z pozostałego stosu po podziale. W tych formach relacja rekurencji to:

\ Displaystyle n_ {i} = {\ Frac {m-1} {m}} n_ {i-1} -1}

Alternatywna forma miała również dwa zakończenia, kiedy poranna dywizja wychodzi na zero i kiedy zostaje jeden orzech dla małpy. Kiedy poranny podział wychodzi równy, ogólne rozwiązanie redukuje się poprzez podobne wyprowadzenie do:

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

Na przykład, gdy i $\$ $displaystyle k = 1} , oryginalny stos ma 1020 kokosów, a po czterech kolejnych$ małpie po w każdym podziale rano zostaje 80 kokosów, więc ostateczny podział wychodzi nawet bez pozostawienia kokosa.

Kiedy poranny podział skutkuje pozostawieniem orzecha, ogólne rozwiązanie jest następujące:

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

gdzie ${0} = - 1}$ $\ displaystyle$ $.$ , jeśli jest nieparzysta, i ${\ displaystyle r_ {0} = 1},$ jest parzysta Na przykład, gdy ${\ displaystyle m = 3}$ , ${\ displaystyle r_ {0} = -1}$ i ${\ displaystyle k = 1}$ , oryginalny stos ma 51 kokosów, a po trzech kolejnych podziałach w nocy z kokosem przydzielonym małpie po każdym podziale, rano zostaje 13 kokosów, więc w końcowym podziale pozostaje kokos dla małpy.

W literaturze omówiono inne warianty post-Williamsa, które określają różne reszty, w tym dodatnie (tj. małpa dodaje kokosy do stosu). Rozwiązaniem jest:

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

gdzie ${\ Displaystyle r_ {0} = 1}$ $dla$ nieparzystych $\$ r $r_ {0} = -1}$ $displaystyle c}$ dla parzystych ${\ Displaystyle m}$ to reszta po każdym dzieleniu (lub liczbie małp), a $jest ujemna$ liczba całkowita ( $,$ jeśli małpy dodają kokosy do stosu)

Inne warianty, w których liczba mężczyzn lub reszty różnią się w zależności od dywizji, generalnie wykraczają poza klasę problemów związanych z małpą i orzechami kokosowymi, chociaż w podobny sposób sprowadzają się one do liniowych równań diofantycznych w dwóch zmiennych. Ich rozwiązania opierają się na tych samych technikach i nie przedstawiają żadnych nowych trudności.

Zobacz też

Problem bydła Archimedesa , znacznie trudniejszy problem diofantyczny
Ostatnie twierdzenie Fermata , prawdopodobnie najsłynniejsze równanie diofantyczne ze wszystkich
Problem z kulą armatnią

Źródła

Antonick, Gary (2013). Małpa i orzechy kokosowe Martina Gardnera w grze liczbowej The New York Times :, 7 października 2013 r.
Pleacher, David (2005). Problem tygodnia: małpa i orzechy kokosowe 16 maja 2005 r
Gardner, Martin (2001). Kolosalna księga matematyki: klasyczne łamigłówki, paradoksy i problemy WW Norton & Company; ISBN 0-393-02023-1
Pappas, Theoni (1993). The Joy of Mathematics: Discovering Mathematics All Around Wide World Publishing, 23 stycznia 1993, ISBN 0933174659
Wolfram Mathworld: Problem małpy i kokosa
Kirchner, RB „Uogólniony problem kokosa”. Amer. Matematyka Miesięczny 67, 516-519, 1960.
Fadiman, Clifton (1962). Matematyczna Sroka , Simon & Schuster
Bogomolny, Alexander (1996) Negatywne orzechy kokosowe i przecięcie węzła

Linki zewnętrzne

wideo Numberphile
Kokosy , kopia historii, która ukazała się w Saturday Evening Post