Piraattien haaksirikko

Viimekertaisessa viikon vaikeassa viisi piraattia yritti päästä sopuun aarteen jakamisesta. Tämä aiheutti ymmärrettävästi pientä närää miesjoukon kesken. Niinpä tunteet olivatkin valmiiksi pinnassa, kun heitä kohtasi onnettomuus: heidän laivansa oli vuoro ajaa karille ja upota. Piraatit onnistuivat ajelehtimaan laudankappaleen varassa pienelle saarelle, jossa he lopen väsyneinä huomasivat, että saari oli täysin autio lukuunottamatta apinaa, joka leikki kookospähkinöillä. Kookospähkinöiden ohella muuta ravintoa ei ollut saatavilla. Piraatit sopivat, että kookospähkinät jaettaisiin aamulla tasan kaikkien kesken.

Ensimmäinen piraatti kuitenkin heräsi keskellä yötä. Hän ajatteli, että kukaan ei huomaisi, jos hän ottaisi oman osuutensa kookoksista jo nyt. Hän jakoi kookokset viiteen osaan, piilotti omansa ja palautti loput kasaan. Yksi kookospähkinä jäi ylitse, ja hän antoi sen apinalle. Sitten piraatti meni takaisin nukkumaan.

Toinen piraatti heräsi vähän myöhemmin. Hänkin jakoi kookokset viiteen osaan ja hautasi oman osuutensa syrjemmälle. Myös nyt jäi yksi kookospähkinä ylitse, ja hän antoi sen apinalle.

Kuva: Loke Seng Hon/Wikimedia Commons (CC BY-SA 3.0)

Kuva: Loke Seng Hon/Wikimedia Commons (CC BY-SA 3.0)

Ja kuten arvata saattaa, vuorollaan yön mittaan myös kolmas, neljäs ja viides piraatti kävivät erottelemassa oman osuutensa. Myös jokainen heistä antoi yhden ylimääräisen kookoksen apinalle.

Aamulla piraatit heräsivät ja huomasivat, että kookospähkinäkasa oli yön mittaan hieman vajunut. He eivät kuitenkaan sanoneet mitään, vaan jakoivat kookokset viiteen osaan. Apinakaan ei jäänyt ilman: yksi kookos jäi ylitse.

Kuinka monta kookospähkinää saarella vähintään oli?


Ratkaisu: Tämä ongelma voidaan ratkaista ainakin parilla eri tavalla. Puhdas kokeileminen eri kookospähkinämäärillä on tietenkin yksi mahdollisuus, mutta luulenpa, että kärsivällisyyden rajat tulevat vastaan…

Lähdetään mieluummin mallintamaan tilannetta. Olkoon kookospähkinöiden lukumäärä n. Apina saa siis jokaisella jakokierroksella yhden pähkinän, jolloin eri jakokerroista saadaan seuraava taulukko.

\begin{array}{|l|l|l|}  \hline  &\mbox{Piraatille}&\mbox{Kasaan}\\  \hline  1&\frac{1}{5}(n-1)&\frac{4}{5}(n-1)\\  2&\frac{1}{5}(\frac{4}{5}(n-1)-1)&\frac{4}{5}(\frac{4}{5}(n-1)-1)\\  3&\frac{1}{5}(\frac{4}{5}(\frac{4}{5}(n-1)-1)-1)&\frac{4}{5}(\frac{4}{5}(\frac{4}{5}(n-1)-1)-1)\\  4&\frac{1}{5}(\frac{4}{5}(\frac{4}{5}(\frac{4}{5}(n-1)-1)-1)-1)&\frac{4}{5}(\frac{4}{5}(\frac{4}{5}(\frac{4}{5}(n-1)-1)-1)-1)\\  5&\frac{1}{5}(\frac{4}{5}(\frac{4}{5}(\frac{4}{5}(\frac{4}{5}(n-1)-1)-1)-1)-1)&\frac{4}{5}(\frac{4}{5}(\frac{4}{5}(\frac{4}{5}(\frac{4}{5}(n-1)-1)-1)-1)-1)\\  \hline  \end{array}

No niin. Aamulla tilanne on siis tämä, eikä yhdelläkään unenpöpperöisellä merirosmolla ole enää mukavaa näiden lausekkeiden kanssa. Tilanne ei ole ollenkaan niin paha kuin miltä se näyttää, sillä voidaan sanoa, että jollakin kokonaisluvulla k pätee

    \[\frac{4}{5}\left(\frac{4}{5}\left(\frac{4}{5}\left(\frac{4}{5}\left(\frac{4}{5}\left(n-1\right)-1\right)-1\right)-1\right)-1\right)=5k+1,\]

eli jos apina saa yhden kookoksen, on jaettava kookoskasa viidellä jaollinen. Nyt yhtälön vasemmalle puolelle muodostuu geometrinen summa, jonka suhdeluku on \frac{4}{5}:

    \[\left(\frac{4}{5}\right)^5 n-\left(\frac{4}{5}\right)^5-\left(\frac{4}{5}\right)^4-\left(\frac{4}{5}\right)^3-\left(\frac{4}{5}\right)^2-\frac{4}{5}\right=5k+1,\]

josta geometrisen summan laskukaavaa hyödyntäen saamme

    \[\left(\frac{4}{5}\right)^5 n-\frac{4}{5}\cdot\frac{1-\left(\frac{4}{5}\right)^5 }{1-\frac{4}{5}}=5k+1.\]

Kun tätä yhtälöä kerrotaan puolittain luvulla 5^5=3125 ja siirrellään hieman termejä yhtäsuuruusmerkin ylitse, saamme seuraavan Diofantoksen yhtälön:

    \[1024n=15625k+11529.\]

Diofantoksen yhtälöllä tarkoitetaan kokonaislukukertoimista vähintään kahden muuttujan yhtälöä, jolle etsitään kokonaislukuratkaisuja. Ne ovat saaneet nimensä noin 200-luvulla eläneen Diofantos aleksandrialaisen mukaan, joka oli aikansa merkittävimpiä matemaatikkoja. Yleistä ratkaisukaavaa näille yhtälöille ei ole olemassa, mutta joitakin erikoistapauksia voidaan ratkaista mekaanisin menetelmin. Onneksi meidän yhtälömme osuu yhteen näistä ”helpoista” tapauksista: nimittäin Diofantoksen yhtälöllä xa+yb=c on aina ääretön määrä ratkaisuja, mikäli lukujen a ja b suurin yhteinen tekijä jakaa luvun c.

Tehdään tekninen muuttujanvaihto m=-k, jolloin yhtälömme voidaan kirjoittaa muotoon 1024n+15625m=11529. Koska 1024=2^{10} ja 15625=5^6, on varmasti näiden suurin yhteinen tekijä 1, joten ratkaisuja on olemassa. Riittää löytää pienin sellainen positiivinen arvo luvulle n, että m on negatiivinen.1

Ensin tarvitaan yksi ratkaisu yhtälölle. Tämä voidaan tehdä joko Eukleideen algoritmin avulla tai sitten ihan vain löytämällä. Äskeisestä yhtälön sievennyksestä voidaan nähdä, että jos n_0=-4 ja m_0=1, on yhtälö tosi. Tällöin yleinen ratkaisu saadaan kaavalla

    \[\begin{cases} n=-4+15625t\\ m=1-1024t \end{cases}, t\in\mathbb{Z}.\]

Nyt sijoittamalla t=1 saadaan n=15621, joka on pienin mahdollinen kookospähkinöiden määrä.

 

  1. Tällöin siis alkuperäinen luku k on positiivinen, kuten kuuluukin.

Vastaa

Sähköpostiosoitettasi ei julkaista. Pakolliset kentät on merkitty *

This site uses Akismet to reduce spam. Learn how your comment data is processed.