Johtosotku

Peter Alexander Robb. CC-BY-NC-SA 3.0.

Laatikossa on 100 sähköjohdon pätkää. Ota laatikosta sattumanvaraisesti yksi johdonpää, sitten sattumanvaraisesti toinen johdonpää, ja yhdistä ne. Tee sama uudestaan niin monta kertaa, että laatikossa ei ole enää yhtään vapaata johdonpäätä. Kuinka monta johtosilmukkaa laatikossa on nyt keskimäärin? Entä jos johtoja onkin tietty tuntematon määrä n?

Joka kierroksella laatikosta valitaan 2 johdonpäätä, jotka yhdistetään. Valinnan jälkeen laatikossa on kaksi johdonpäätä vähemmän. Jos johtoja on n kpl, kierroksia käydään myös n kpl, ennen kuin kaikki johdonpäät on käyty läpi.

Jokaisella kierroksella on kaksi vaihtoehtoa:
a) Valitaan sattumalta saman johdon molemmat päät, jolloin syntyy silmukka.
b) Valitaan kahden eri johdon päät, jolloin muodostuu pidempi johto.

Tapausten a) ja b) todennäköisyydet riippuvat vain siitä kuinka mones kierros on menossa. Jos jäljellä on x johtoa, on tapauksen a) todennäköisyys 1 / (2x - 1). Ensimmäinen johdonpää valitaan 2x:stä vaihtoehdosta ja jälkimmäinen (2x - 1):stä vaihtoehdosta, joista vain yksi on jo valitun johdon toinen pää.

Kun silmukan syntymisen todennäköisyys per kierros on tiedossa, voidaan laskea silmukoiden määrän odotusarvo. Käydään läpi kaikki kierrokset yhdestä n:ään ja summataan kullakin kierroksella syntyvän silmukan todennäköisyys: 1 / (2n - 1) + 1 / (2n - 3) + ... + 1, eli:

100:n johdon tapauksessa summaksi tulee n. 3,3. Syntyy siis keskimäärin vain 3 silmukkaa. Samalla kaavalla voidaan myös todeta, että 1000:n johdon tapauksessakin silmukoita syntyisi vain 4 kpl.

Viiniä ruukusta toiseen

Pguerin. CC-BY-SA 3.0.

Sinulla on kolme viiniruukkua: 12 litran, 8 litran ja 5 litran ruukut. 12 litran ruukku on täynnä viiniä ja muut kaksi tyhjiä. Viini pitäisi saada jaettua tasan kahteen ruukkuun, siis 6 litraa yhteen ja 6 litraa toiseen ruukkuun. Miten tämä onnistuu?

Kaada 12 litraisesta ruukusta 8 litran ruukku täyteen. Kaada sitten 8 litran ruukusta 5 litran ruukku täyteen. Nyt ruukuissa on 4, 3 ja 5 litraa.

Kaada 5 litran astian sisältö 12 litran ruukkuun. Kaada 8 litran ruukussa olevat 3 litraa 5 litran ruukkuun ja sitten 12 litran ruukusta 8 litran ruukku täyteen. Nyt ruukuissa on 1, 8 ja 3 litraa.

Kaada 8 litran ruukusta 5 litran ruukku täyteen ja täysinäinen 5 litran ruukku 12 litran ruukkuun. Nyt 12 litran ja 8 litran ruukuissa on molemmissa 6 litraa viiniä.

Päivämääräpalindromi

Päivämäärä 10. helmikuuta 2001 on eräänlainen palindromi, jos sen kirjoittaa muodossa 10.02.2001 (eli päivä.kuukausi.vuosi). Mikä on lähin sitä edeltävä päivämäärä, joka on myös palindromi?

Lisätehtävä: päivämäärä 2. lokakuuta 2001 on myös palindromi, jos se kirjoitetaan muodossa 2001-10-02 (eli vuosi-kuukausi-päivä). Mikä on lähin sitä edeltävä palindromipäivämäärä?

Oletetaan, että kaikille vuosille on käytössä samat säännöt kuin nykyään, eli nykyiset kuukaudet ja kuukausien pituudet.

Ensimmäisessä tehtävässä lähin päivämäärä ei ole kovin lähellä. Esimerkiksi vuosi 2000 ei käy, koska päiväksi tulisi 00, eikä mikään vuosi vuosisadalta 1900 käy, koska silloin kuukauden täytyisi olla 91. Koska vuosisadan täytyy olla sama kuin päivämäärän kuukausiosa toisin päin käännettynä, lähin sopiva vuosisata on 1100.

Etsitään vielä vuosikymmen ja vuosi. Jos valittaisiin suurin mahdollinen kuukauden päivä, tulisi päivämääräksi 31.11.1113. Mutta koska tarkoitus on löytää suurin vuosiluku eikä suurin päivä, kannattaa valita se päivä, joka on toisin päin käännettynä suurin mahdollinen eli 29. Päivämäärä on siis 29.11.1192.

Lisätehtävän ratkaisu etenee vastaavasti, mutta tällä kertaa päiväosa määrää vuosisadan ja kuukausiosa vuosikymmenen ja vuoden. Suurin mahdollinen vuosisata ennen vuosisataa 20 on 13. 14 tai suurempi ei käy, koska silloin päivän pitäisi olla 41 tai suurempi.

Vuosikymmen- ja vuosiosan täytyy olla sellainen, että se on toisin päin luettuna kelvollinen kuukausi. Jos otetaan suurin kuukausi eli 12, saadaan vuosi 1321. Se ei kuitenkaan ole suurin vaihtoehto. Suurin on 09, jolloin saadaan vuosi 1390. Päivämäärä olisi siis 1390-09-31.

Vai onko vielä jotain pielessä? On kyllä, sillä syyskuussa on vain 30 päivää. Siispä täytyy mennä vielä vuosi ja kuukausi kauemmas. Oikea vastaus on 1380-08-31.

Karibianmeren kauhut

Oren neu dag. CC-BY-SA 3.0

Viisi merirosvoa ryöstelee laivoja Karibianmerellä. Viimeisimmältä ryöstöretkeltään merirosvot saivat saaliiksi 100 kultarahaa. He jakavat saaliin seuraavalla tavalla.

Vanhin ehdottaa miten saalis jaetaan. Jos vähintään puolet merirosvoista hyväksyy jaon, se jää voimaan. Jos yli puolet merirosvoista on eri mieltä, he käyvät vanhimman kimppuun ja pistävät hänet kävelemään lankulle. Sen jälkeen jäljelle jääneistä vanhin saa vuorostaan ehdottaa jakoa. Sama menettely jatkuu kunnes sopiva jakotapa löytyy.

Kaikki merirosvot ovat äärimmäisen ahneita ja hyvin älykkäitä. Kukaan heistä ei tietenkään halua menettää henkeään. Minkälaista jakoa vanhimman merirosvon kannattaa ehdottaa?

Kysymys saattaa kuulostaa aluksi epämääräiseltä, mutta tähän on olemassa selkeä ja perusteltu vastaus. Vanhimman merirosvon täytyy saada kaksi muuta merirosvoa puolelleen, jotta vähintään puolet kannattaisi hänen ehdottamaansa jakoa. Samalla hän yrittää saada itselleen niin suuren osan rahoista kuin mahdollista. Ketkä kaksi hänen täytyy saada tyytyväiseksi ja tarkalleen kuinka paljon heille täytyy antaa, jotta voi olla varma heidän tuestaan?

Mietitään ensin tapaukset, joissa merirosvoja olisikin 1, 2, 3 tai 4.

Jos merirosvoja on yksi, hän ottaa itselleen koko saaliin eikä minkäänlaista äänestystä tarvita.

Jos merirosvoja on kaksi, vanhempi heistä ottaa kaiken itselleen, koska äänestyksessä hänen oma äänensä riittäisi.

Jos merirosvoja on kolme, vanhimman pitää saada puolelleen yksi muista. Kaikki tietävät, että toiseksi vanhin saa kaiken, jos vuoro siirtyy hänelle. Niinpä vanhin ei voi mitenkään saada toiseksi vanhinta puolelleen. Sen sijaan nuorin kolmesta ei saa mitään, jos toiseksi vanhin pääsee tekemään jaon. Siispä vanhimman on helppo saada nuorin puolelleen. Yksikin kultaraha riittää.

Jos merirosvoja on neljä, vanhimman pitää saada yksi muista puolelleen. He kaikki tietävät, että jos vuoro siirtyy toiseksi vanhimmalle, saa hän 99 kultarahaa, nuorin yhden, ja toiseksi nuorin jäisi tyhjin käsin. Vanhin voisi saada nuorimman puolelleen tarjoamalla 2 kultarahaa, eli enemmän kuin toiseksi vanhin antaisi. Vanhimman on kuitenkin vielä helpompi taivutella toiseksi nuorin puolelleen. Riittää kun tarjoaa jaossa yhden kultarahan.

Tästä päästäänkin viiden merirosvon tapaukseen. Vanhin tarvitsee kahden muun merirosvon tuen säilyttääkseen henkensä. He kaikki tietävät, että jos vuoro siirtyy toiseksi vanhimmalle, saa hän 99 kultarahaa ja toiseksi nuorin yhden. Siispä vanhimman kannattaa tavoitella kolmanneksi vanhimman ja kaikista nuorimman tukea. Siihen riittää yksi kultaraha merirosvoa kohti, sillä jos he eivät hyväksy tarjousta, he jäävät kokonaan ilman.

Vanhimman merirosvon ehdotus on siis se, että hän itse ottaa 98 kultarahaa, kolmanneksi vanhin saa yhden kultarahan ja nuorin yhden kultarahan.