0

Rekursiivinen rekursio

Kollegani Petri Kuukkanen antoi minulle melkoisen pirulaisen ratkottavaksi. Näin se kuuluu:

Järjestä luvut 1, 2, 3, \ldots, 9 lukujonoksi a_1, a_2, a_3, \ldots, a_9 niin, että

  • a_2=2 ja
  • a_n=a_{a_{n-1}}-1, kun n=2, 3, \ldots, 9.

Kuva: Bird Eye/Flickr (CC BY 2.0)

0

Paikat sekaisin

Teatterisalissa on 100 numeroitua paikkaa. Loppuunmyytyyn esitykseen ensimmäisenä saapuva H. hukkaa paikkalippunsa heti saliin päästyään, joten hän istuu sattumanvaraiselle paikalle. Tämän jälkeen kaikki muut istuvat omille paikoilleen, tai mikäli paikalla istuu jo joku, hekin asettuvat sattumanvaraiselle istuimelle. Millä todennäköisyydellä viimeisenä saliin saapuva Toni pääsee omalle paikalleen?

Kuva: Thomas Hawk/Flickr (CC BY-NC 2.0)


Ratkaisu: Niin uskomattomalta kuin se kuulostaakin, Toni saa oman paikkansa 50 prosentin todennäköisyydellä. Lähdetään yksinkertaisesta tilanteesta: jos salissa olisi vain kaksi paikkaa, H. istuisi omalleen ja Tonin paikalle yhtä todennäköisesti. Mutta kun paikkojen määrää lisätään, ei edelleenkään ole väliä kuin näillä kahdella paikalla!

Jos H. istuu omalle paikalleen tai Tonin paikalle, istuvat kaikki muut oikeille paikoille. Jos taas H. istuu esimerkiksi Kössin paikalle, istuvat kaikki ennen Kössiä istuutuvat omille paikoilleen, ja vasta Kössin on päätettävä, minne istuu. Jos Kössi istuu H:n paikalle, saa Toni oman paikkansa, ja jos taas Kössi istuu Tonin paikalle, Toni ei saa sitä. Näissä molemmissa tapauksissa kaikki loput saavat olan paikkansa. Jos Kössi istuu muualle, esimerkiksi Emilian paikalle, on Emilian hänen jälkeensä tehtävä aivan vastaava ratkaisu. Eli lopullisia päätöksiä on ainoastaan kaksi: istuako H:n paikalle vai Tonin paikalle, muut päätökset matkan varrella vain pitkittävän tämän päätöksen hetkeä.

0

Tulilanka palaa!

Kahdesta tulilangasta tiedetään, että kun ne sytytetään jommasta kummasta päästä, niiltä kestää palaa loppuun täsmälleen tunnin verran. Lankojen sisäinen palonopeus on täysin sattumanvarainen ja jokainen lanka on erilainen. Kuinka näiden lankojen avulla mitataan 45 minuuttia?

Kuva: Epic Fireworks / Flickr (CC BY 2.0)


Ratkaisu: Sytytä toinen lanka molemmista päistä ja toinen lanka toisesta päästä. Molemmista päistä sytytetyn langan loppuunpalamiseen kuluu 30 minuuttia. Sytytä tällöin toisenkin langan toinen pää, jolloin lanka palaa loppuun 15 minuutissa. Yhteensä paloaika on siis 45 minuuttia.

Tämä pulma tuli vastaan folj.com-sivustolla, mutta olen kyllä törmännyt siihen jossain muuallakin joskus.

1

Nimekäs lapsi

Herra H. tapasi kadulla entisen luokkatoverinsa, joka työnsi lastenvaunuja. He eivät olleet kohdanneet kertaakaan miltei 20 vuoteen. He kertoilivat kuulumisia tovin. Luokkatoveri oli oleskellut lähinnä Saksassa ja hänellä oli saksalainen puolisokin. H. kysyi, mikä oli heidän pienen tyttärensä nimi. Toveri kertoi heidän nimenneen tytön äitinsä mukaan. ”Hei, Laura!” H. sanoi vaunussa hymyilevälle tyttöselle. Miten H. tiesi hänen nimensä, vaikka ei tuntenut luokkatoverin puolisoa?


Ratkaisu: H:n luokkatoverin nimi oli Laura, joten tytönkin nimi oli Laura.

0

Kadonnut luku

kummalukuTämä erityisen kaunis pulma on peräisin Nob Yoshigaharalta (1930–2004), japanilaiselta ongelmaspesialistilta. Minä löysin sen jälleen kerran Alex Bellosin kautta.

Mikä luku sopii kysymysmerkin paikalle? Alhaalla oleva luku 7 ei ole virhe.


Ratkaisu: Puuttuva luku on 12. Se on siihen johtavien lukujen numeroiden summa, kuten kaikissa muissakin kohdissa.

0

Hullut Hattuset

VillelläMiihkalilla ja Leolla on laatikossa viisi hattua: kaksi keltaista ja kolme punaista. He ottavat silmät kiinni laatikosta yhden hatun päähänsä ja sulkevat sen jälkeen laatikon. He eivät näe omaa hattuaan eivätkä laatikkoon jääneitä hattuja, mutta toistensa hatut he näkevät. Käydään seuraava keskustelu:

Leo: ”En tiedä hattuni väriä.”
Miihkali: ”En tiedä hattuni väriä.”
Ville (joka näkee kaksi punaista hattua): ”Tiedän hattuni värin!”

Minkä värinen hattu Villellä on?

Kuva: Tomi Palsa /Hattuset.net

Kuva: Tomi Palsa/Hattuset.net


Ratkaisu: Leo voisi tietää hattunsa värin ainoastaan, jos hän näkisi kaksi keltaista hattua. Miihkali tietää tämän, joten hän tietää, että Leo näki korkeintaan yhden keltaisen hatun. Leon hatun Miihkali näkee punaiseksi, joten keltainen hattu voi olla joko Miihkalin tai Villen päässä. Jos Villen hattu olisi keltainen, voisi Miihkali päätellä oman hattunsa punaiseksi, mutta koska hän ei näin voi tehdä, on Villelläkin pakko olla punainen hattu.

3

Järvinen, Mäkinen ja Virtanen

Sain käsiini Alex Bellosin upouuden pulmakirjan Can You Solve My Problems? (Guardian Books, 2016), jossa jäin ensimmäisen kerran jumiin heti ensimmäisellä sivulla (tästä ongelmasta myöhemmin lisää). Ensivaikutelma kirjasta on, että nyt ollaan pulmakirjallisuuden tulevan klassikon äärellä. Huippulaatua!

Mutta asiaan. Seuraava pulma löytyy Bellosin kirjasta. Se on laatinut Henry Ernest Dudeney, ja se on julkaistu vuonna 1930 lontoolaisessa The Strand Magazinessa.1 Dudeneyn pulma saavutti aikanaan maailmanlaajuisen suosion. Tässä se tulee.

Järvinen, Mäkinen ja Virtanen ovat junan kuljettaja, konduktööri ja myyjä, eivät tosin välttämättä tässä järjestyksessä. Sattumalta junassa matkustavat herrat Järvinen, Mäkinen ja Virtanen, joihin jatkossa viitataan arvonimellä herra. Tiedetään seuraavaa:

  • Herra Virtanen asuu Tampereella.
  • Myyjä asuu Tampereen ja Helsingin puolessavälissä.
  • Herra Mäkinen tienaa 70000 euroa vuodessa.
  • Järvinen voittaa konduktöörin biljardissa.
  • Myyjän seinänaapuri (eräs matkustajista) tienaa tasan kolminkertaisesti myyjään verrattuna.
  • Myyjän sukunimikaima asuu Helsingissä.

Viikon vaikea kysymys on tietenkin, että mikä on junan kuljettajan nimi.

Kuva: Tomi Lattu/Flickr (CC BY 2.0)

Kuva: Tomi Lattu/Flickr (CC BY 2.0)


Ratkaisu: Koska Järvinen voittaa konduktöörin biljardissa, ei Järvinen ole konduktööri. Koska herra Mäkinen tienaa tasan 70000 euroa, ei hän voi olla myyjän seinanaapuri, koska 70000 ei ole kolmella jaollinen luku. Tämän vuoksi hänen on oltava Helsingissä asuva myyjän sukunimikaima, koska herra Virtanen asuu Tampereella. Myyjä on siis Mäkinen. Ja koska Järvinen ei ole myyjä eikä konduktööri, on hän junan kuljettaja.

0

Pöytätennispäivä

Hienoista hiljaiseloa viettänyt Pulmakulma palaa viimein syyslomalta kauniin pulman kanssa. Tämä löytyi jälleen Alex Bellosin palstalta The Guardianista.

Hannu, Karja Hristo viettävät koko päivän pöytätennistä pelaten. Säännöt ovat selvät: kahden pelatessa kolmas odottaa vuoroaan, voittaja jää pöydälle, häviäjä siirtyy odotusvuoroon. Päivän lopuksi he laskevat, montako peliä kukin on pelannut. Tulokset ovat seuraavat:

  • Hannu: 10 peliä
  • Kari: 15 peliä
  • Hristo: 17 peliä

Viikon helppo pulma on selvittää, kuka hävisi päivän toisen pelin.

Kuva: Jean-Cristophe Le Brun/Flickr (CC BY 2.0)

Kuva: Jean-Cristophe Le Brun/Flickr (CC BY 2.0)


Ratkaisu: Koska 10+15+17=42 ja koska jokaisessa pelissä on kaksi pelaajaa, pelasivat Hannu, Kari ja Hristo päivän aikana 21 peliä. Kukin pelaaja on ollut mukana vähintään joka toisessa pelissä, joten riippuen siitä, onko pelaaja aloittanut peli- vai odotusvuorossa, on pelejä kerryttävä vähintään 11 tai 10. Koska Hannu on pelannut vain 10 peliä, on hän aloittanut lepovuorossa ja hävinnyt kaikki pelinsä. Toisen ottelun häviäjä on siis Hannu.

0

Kuninkaan yt-neuvottelut

Vierailimme vaimoni vanhassa kotitalossa, jossa tein huiman löydön: hänen vanhoista tavaroistaan löytyi kenenpä muunkaan kuin Lewis Carrollin The Complete Illustrated Lewis Carroll (Wordsworth Editions, 1996). Kirjaa selatessani törmäsin noin vuodelta 1870 peräisin olevaan Puzzles from Wonderland -tekstiin, jossa Carroll riimittelee hauskasti seitsemän pulmaa vastauksineen. Niistä viimeinen on tässä.1

Kuningas huomasi, että hänen rahansa olivat lähes lopussa, ja että hänen oli elettävä säästäväisemmin. Hän päätti irtisanoa suurimman osan neuvonantajistaan. Heitä oli satoja – hienoja vanhoja miehiä juhlavissa vihreissä samettiviitoissa, joissa oli kultaiset napit. Neuvonantajissahan ei varsinaisesti ollut muuta vikaa kuin että he puhuivat keskenään aivan ristiin, kun heidän neuvojaan kysyttiin; lisäksi he olivat järkyttävän kovia syömään ja juomaan. Kaikkiaan kuningas oli ihan tyytyväinen päästessään heistä eroon. Mutta valtakunnassa oli eräs ikivanha laki, jota kuningaskaan ei tohtinut rikkoa. Laki määräsi neuvonantajien määrästä seuraavaa:

”Seitsemän molemmista silmistä sokeaa:

Kaksi yhdestä silmästä sokeaa:

Neljä jotka näkevät molemmilla silmillä:

Yhdeksän jotka näkevät yhdellä silmällä.”

Mikä oli neuvonantajien vähimmäismäärä?

Kuva: Wikimedia Commons

Kuva: Wikimedia Commons


Ratkaisu: Neuvonantajia tarvitaan vähintään kuusitoista, sillä kokonaan sokea voidaan laskea toisesta silmästä sokeaksi ja kokonaan näkevä voidaan laskea toisella silmällä näkeväksi. Mutta annetaanpa Lewis Carrollin vastata ihan omin sanoin:

Five seeing, and seven blind
Give us twelve, in all, we find;
But all of these, ’tis very plain,
Come into account again.
For take notice, it may be true,
That those blind of one eye are blind for two;
And consider contrariwise,
That to see with your eye you may have your eyes;
So setting one against the other—
For mathematician no great bother—
And working the sum, you will understand
That sixteen wise men still trouble the land.

5

Pyörivä pöytä ja helisevä tiuku

Pöydän pyörittely on matemaattisessa mielessä sangen kiehtovaa, oli sitten kyseessä epätasainen keittiön lattia tai väärässä järjestyksessä istuvat ritarit. Myös tässä ongelmassa tarvitsee pyöritellä pöytää.

Neliön muotoisen pöydän jokaisessa nurkassa on kolo, johon on asetettu juomalasi joko ylösalaisin tai oikein päin. Omituisella mekaniikalla laseihin on kytketty pieni tiuku, joka helähtää, mikäli kaikki lasit ovat samoin päin. Koloihin ei näe, mutta niihin pystyy työntämään käden niin, että tunnustelemalla selviää, kuinka päin lasi on. Lisäksi lasin pystyy kääntämään. Pöytää voidaan pyörittää keskipisteensä ympäri niin, että kun pyöriminen loppuu, ei mitenkään voida paljaalla silmällä päätellä, mikä koloista on mikäkin. Omituinen häkkyrä siis.

Pelataan seuraavanlaisin säännöin: pyöräytetään pöytää, jonka jälkeen työnnetään kädet yhtä aikaa mihin tahansa kahteen eri koloon. Koloissa voi tunnustella laseja ja sen jälkeen kääntää joko molemmat lasit tai vain toisen. Kumpaakaan lasia ei ole pakko kääntää. Tarkasteltavat kolot on kuitenkin valittava samanaikaisesti ja ennen kuin menee räpeltämään mitään. Tavoite on saada tiuku helisemään. Alkutilanne on muuten sattumanvarainen, mutta voidaan olettaa, että kaikki lasit eivät ole samoin päin (sillä silloinhan tiuku helisisi jo).

Mikä on pienin määrä pyöräytyksiä, jonka jälkeen tiu’un saa varmasti helisemään? Miten se tehdään?

Myös tämä pulma on Martin Gardnerilta. Poimin sen mainiosta teoksesta The Colossal Book of Short Puzzles and Problems (W.W. Norton & Co, 2006). Pulman esitettyään Gardner jatkaa, että jos pöydässä olisi vain kaksi koloa, olisi ratkaisu tietenkin triviaali: kädet koloihin ja lasit samoin päin. Myöskään kolmikoloinen pöytä ei ole kovin vaikea ratkaistava. Jos ensimmäisellä yrityksellä molemmat lasit ovat samoin päin, käännetään ne toisin päin ja johan helisee. Jos taas ne ovat eri päin, käännetään ne molemmat esimerkiksi alassuin, jonka jälkeen toisella yrityksellä helinä on varma. Edelleen Gardner toteaa, että voidaan osoittaa, ettei viisikoloista pöytää pysty ratkaisemaan – ainakaan alle kolmekätisenä pyörittäjänä.


Ratkaisu: Viisi pyöräytystä riittää aina. Toimitaan näin:

  1. Otetaan vastakkaisissa koloissa olevat lasit ja käännetään ne molemmat ylöspäin. Jos tiuku ei nyt helise, jatketaan pyörittämistä.
  2. Otetaan vierekkäiset lasit ja käännetään ne ylöspäin, elleivät ne jo ole. Jos tiuku ei vieläkään helise, nyt tiedetään, että kolme laseista on ylöspäin ja yksi alaspäin. Pyöritetään pöytää uudestaan.
  3. Valitaan jälleen vastakkaiset kolot. Jos toinen laseista on alaspäin, käännetään se ja tiuku helisee. Jos taas molemmat ovat ylöspäin, käännetään toinen, jolloin välttämättä kaksi vierekkäistä lasia on ylöspäin ja kaksi vierekkäistä alaspäin. Pyöritetään edelleen.
  4. Valitaan kaksi vierekkäistä koloa. Jos lasit ovat samoin päin, käännetään molemmat ja tiuku helisee. Jos ne taas ovat eri päin, käännetään jälleen molemmat, jolloin varmasti kaksi vastakkaista lasia on ylöspäin ja toiset kaksi vastakkaista alaspäin. Pyöritetään.
  5. Valitaan vastakkaiset lasit ja käännetään ne molemmat toisin päin. Tiuku helisee.