kombinatoriikka

0

Pormestarinvaali

|

Tuomo ja Mikko ovat pormestarinvaalin toisella kierroksella. Mikko saa lopulta m ääntä ja Tuomo t ääntä. Oletetaan, että annetut äänet nostetaan vaaliuurnasta yksi kerrallaan ja pidetään jatkuvasti kirjaa laskennan edistymisestä. Millä todennäköisyydellä ensimmäisen nostetun äänen jälkeen äänet ovat jossain ääntenlaskennan vaiheessa tasan?

 

0

Numerot järjestykseen

|

Kahdeksannumeroisessa luvussa on kaksi ykköstä, kaksi kakkosta, kaksi kolmosta ja kaksi nelosta. Ykköset ovat yhden numeron päässä toisistaan, kakkoset kahden numeron, kolmoset kolmen numeron ja neloset neljän numeron päässä toisistaan. Mikä luku on kyseessä?

Ratkaisu: Luku on 41312432 tai tämän peilikuva 23421314. Tämän pulman lähde on Futility Closet.

 

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ä.

2

Saunavuoro

|

Tämänkertainen pulmamme on Pulmakulman ystävän Toni Vaahteran käsialaa. Kiitos, Toni!

Tuomas, Mikko, Johannes, Antti ja Kössi istuvat saunan lauteilla. Löylyttely sujuu mukavissa merkeissä kunnes löylykauha kolahtaa kiulun pohjaan. Millä keinolla saunojat voivat siltä istumalta reilusti arpoa kuka saunojista hakee vettä? Luonnollisesti älypuhelimet, nopat ja kolikot ja muut apuvälineet on jätetty pukuhuoneen puolelle.

Kuva: Wikimedia Commons (Public Domain)

Kuva: Wikimedia Commons (Public Domain)

Ratkaisu: Viiden hengen kivi-sakset-paperi ei oikein kuulosta hyvältä ratkaisulta. Mutta sormileikillä asia voidaan kuitenkin kätevästi ratkaista. Sovitaan, että kukin viidestä saunojasta edustaa yhtä jäännösluokkaa modulo 5. Eli kun kokonaislukua jaetaan viidellä, voi jakojäännös olla 0, 1, 2, 3 tai 4, ja näistä jäännösluokista yksi voi edustaa kutakin saunojaa. Sitten yhtä aikaa kukin paljastaa yhdestä viiteen sormea. Sormet lasketaan yhteen ja katsotaan, mikä on jakojäännös.

Sormileikki on reilu tapa. Erilaisia sormiyhdistelmiä on 5^5=3125 kappaletta, ja summat jakautuvat tasan kaikille viidelle jäännösluokalle, 625 mahdollista sormisummaa kullekin. Nyt on huomattava, että jokaisen saunojan on näytettävä vähintään yksi sormi, sillä jos pelkkä nyrkkikin sallittaisiin, olisi mahdollisia yhdistelmiä 6^5=7776 kappaletta, josta jäännösluokalle 0 tulisi 1556 sormisummaa, kun taas kaikille muille luokille tulisi vain 1555 sormisummaa. Sen sijaan peli sallisi tässä tapauksessa kuudennen saunojan.1

Olen aika pitkään ollut sitä mieltä, että jo kahden pelaajan kesken kivi-sakset-paperi on epätyydyttävä tapa arpoa. Tasapeleistä päästäisiin heti eroon pelaamalla parillista ja paritonta, jonka säännöt ovat vastaavat kuin saunapelimme. Parillisessa ja parittomassa puolestaan on ehdottomasti sallittava nollan sormen vaihtoehtokin, muutoin peli suosii paritonta. Tähän peliin törmäsin ensimmäisen kerran joskus parikymmentä vuotta sitten, mahdollisesti jossakin Hale & Pace -sarjan sketsissä, mutta varmoja muistikuvia ei ole. Joka tapauksessa olen vuosikausia pyrkinyt välttämään kivi-sakset-paperia arvontatilanteissa, mutta jotenkin parillinen ja pariton ei vain ole saavuttanut haluamaani arvostusta toveripiirissäni. Mutta ehkäpä nyt tämän saunajutun myötä…

0

Pimeät sukat

|

Pimeän vaatehuoneen sukkalaatikossa on 16 punaista sukkaa ja 20 sinistä sukkaa. Montako sukkaa minun pitää vähintään laatikosta ottaa, jotta saan varmasti parin samanvärisiä sukkia?

No. Tämä oli ihan liian helppo. Laitetaan vähän lisää panoksia. Laatikossa on yhtä monta sinistä ja punaista sukkaa. Tiedetään, että pienin määrä, joka sukkia pitää nostaa laatikosta, jotta saataisiin ainakin kaksi samanväristä sukkaa, on sama kuin määrä, joka pitää nostaa, jotta saataisiin varmasti kaksi eriväristä sukkaa. Montako sukkaa laatikossa on?

Ratkaisu: Ensimmäisen kysymyksen vastaus on kolme. Toisen kysymyksen vastaus on neljä.

0

Kutsuvieraiden kättelyt

|
Kuva: Dan Beard/Cosmopolitan Magazine (Public Domain), via Wikimedia Commons

Kuva: Dan Beard/Cosmopolitan Magazine (Public Domain), via Wikimedia Commons

Palataanpa jälleen klassisten Martin Gardnerin pulmien pariin.

Kutsuilla oli minun ja puolisoni lisäksi neljä muuta pariskuntaa. Kuten kohteliasta on, osa vieraista tervehti toisiaan kutsujen aluksi kätellen. Kukaan ei kätellyt puolisoaan, eikä kukaan kätellyt kenenkään kanssa kahdesti. Kättelyiden jälkeen kysyin kaikilta muilta, kuinka monen henkilön kanssa he olivat kätelleet. Jokainen vastasi eri lukumäärän. Monenko kanssa puolisoni kätteli?

 

Ratkaisu: Yhden henkilön suurin määrä kättelyitä voi olla kahdeksan. Koska minun lisäkseni henkilöitä on yhdeksän, heidän kättelymääränsä ovat varmasti 0, 1, 2, 3, 4, 5, 6, 7 ja 8. Joukossamme on siis joku, joka kättelee kaikkia muita paitsi omaa puolisoaan. Tällöin hänen puolisonsa täytyy olla se, joka ei kättele ketään, sillä kaikki muut ovat kätelleet jo ainakin kerran.

Joukosta löytyy myös seitsemän kertaa kätellyt henkilö. Hän kättelee muita paitsi puolisoaan ja nolla kertaa kätellyttä. Nyt kaikki muut paitsi seitsenkertaisen puoliso (ja nollasti kättelevä) ovat kätelleet ainakin kahdesti. Siis seitsemän kättelyn pari on kerran kättelevä. Vastaavasti kuuden kättelyn pari on kahdesti kättelevä ja viidesti kättelevän pari kolmesti kättelevä.

Tämän jälkeen jäljelle jää pariskunta, jonka molemmat puoliskot kättelevät neljästi. Siis puolisoni ja minä.

0

Muurahaisen vaikea juoksu

|

KuutioMuurahainen lähtee liikkeelle kuution kärjestä A ja etenee kuution särmiä pitkin. Kun muurahainen tulee johonkin kärkeen, se valitsee sattumanvaraisesti seuraavan särmän, jota pitkin se lähtee kulkemaan (se voi siis myös palata takaisin kohti kärkeä, josta se juuri lähti). Millä todennäköisyydellä muurahainen päätyy kärkeen B kuljettuaan täsmälleen seitsemän särmää?

(HUOM! Muurahaisen ei tarvitse olla seitsemännen särmän jälkeen ensimmäistä kertaa kärjessä B.)

Tämä ongelma on huomattavasti haastavampi kuin Muurahaisen helppo juoksu, joten suosittelen tutustumaan tähän vasta helpolla juoksulla lämmiteltyäsi.

Ratkaisu: Harva ongelma (edes tässä blogissa) on saanut minut innostumaan yhtä paljoa kuin tämä. Syy siihen on seuraavassa kerrassaan hurmaavassa tavassa ratkaista pulma.

Koska kaikki kulkureitit ovat yhtä todennäköisiä, päästään ongelman ratkaisussa soveltamaan klassista todennäköisyyttä. Kun liikutaan seitsemän särmää, ja jokaisessa kärjessä on kolme vaihtoehtoa seuraavaksi suunnaksi, on erilaisia kulkureittejä tuloperiaatteen nojalla 3^7=2187 kappaletta. Selvitetään seuraavaksi, kuinka moni näistä reiteistä on suotuisia tapauksia muurahaisellemme.

Olkoon piste A=(0,0,0) ja piste B=(1,1,1). Jokaisen särmän liikkuminen muuttaa täsmälleen yhtä pisteen kolmesta koordinaatista, nollasta ykköseksi tai ykkösestä nollaksi. Tavoitteemme olisi siis se, että kaikkia koordinaatteja olisi seitsemän särmän jälkeen muutettu pariton määrä kertoja. Tämä voidaan tehdä kahdella ja vain kahdella erilaisella tavalla:

  1. Yhtä koordinaattia muutetaan viidesti ja kahta muuta kerran.
  2. Kahta koordinaattia muutetaan kolmesti ja yhtä kerran.

Lasketaan sitten, montako erilaista reittiä tapauksiin 1 ja 2 sisältyy. Viidesti muutettava koordinaatti voidaan valita kolmella tavalla. Edelleen kombinatoriikkaa soveltaen viisi vaihtoa seitsemästä voidaan valita \binom{7}{5}=\frac{7!}{5!2!}=21 tavalla. Jäljelle jäävien koordinaattien vaihdoista ensimmäinen voidaan valita kahdesta jäljellä olevasta vaihtopaikasta, jolloin viimeiselle koordinaatin vaihdolle jää vain yksi paikka. Näin ollen tapaukselle 1 suotuisia reittejä on

    \[3\cdot\binom{7}{5}\cdot 2\cdot 1=126.\]

Vastaavaa päättelyä noudattaen tapaukseen 2 sisältyy 3\cdot\binom{7}{3}\cdot \binom{4}{3}\cdot 1=420 mahdollista reittiä. Koska tapaukset 1 ja 2 ovat erilliset, eli niihin ei sisälly samoja reittejä, on reittien kokonaismäärä 126+420=546 Näin ollen todennäköisyys sille, että seitsemännen särmän jälkeen ollaan kärjessä B on klassisen todennäköisyyden mukaan

    \[\frac{546}{2187}=\frac{182}{729}=0,2496\ldots\approx 0,25.\]

Tästäkin ongelmasta iso kiitos Thomas Poveylle, jonka pulmakirjaa Professor Povey’s Perplexing Problems olen nyt pari viikkoa iltaisin jatkuvasti selaillut. Kirjassa on kymmeniä tiukkoja matematiikan ja fysiikan tehtäviä, jotka on suunnattu korkeakouluopintojen kynnyksellä oleville ongelmanratkaisusta innostuneille opiskelijoille. Tai sitten heidän opettajilleen. Erittäin suositeltava opus.

PS. Eräs opiskelijani heitti suunnilleen välittömästi ongelman kuultuaan arvauksen, että vastaus ei varmaankaan ole \frac{1}{4}, mutta että se on sinnepäin. Aivan oikein. Parittomalla siirtomäärällä kuutiossa on vain neljä kärkeä, joissa muurahainen voi olla. Mitä suuremmaksi siirtojen määrä kasvaa – kunhan niitä on vain pariton määrä – sitä lähempänä todennäköisyys päätyä kärkeen B on arvoa \frac{1}{4}.

7

Pyöreän pöydän ritarit – ratkaisu

|

Suuren salin pyöreän pöydän ympärillä oli 24 tasaisin välimatkoin aseteltua nimettyä paikkaa. Kun pyöreän pöydän ritarit saapuivat saliin, oli valitettavasti pimeää, ja kaikki ritarit istuivat vahingossa väärille paikoille. Osoita, että pöytää kiertämällä saadaan ainakin kahden ritarin nimilaput oikeille paikoille.

Tässä ongelmassa vaikuttaa yksinkertaisuudestaan huolimatta sangen vahva matemaattinen periaate, jota kutsutaan kyyhkyslakkaperiaatteeksi. Toisinaan sitä kutsutaan myös kehittäjänsä Johann Peter Gustav Lejeune Dirichlet’n (1805–1859) mukaan, mutta pitäytykäämme tässä hieman hauskemmassa – ja silti yleisesti tunnetussa – nimityksessä. Kyyhkyslakkaperiaatteessa on kyse siitä, että jos m asiaa pitää laittaa n laatikkoon ja m>n, niin ainakin yhteen laatikkoon tulee ainakin kaksi asiaa.

Kuinka pyöreän pöydän ritarit sitten liittyvät kyyhkyslakkaperiaatteeseen? Yleisyydestä luopumatta voidaan sopia, että pöytää kierretään esimerkiksi vastapäivään. Nyt kukaan ritareista ei ole omalla paikallaan, joten jokainen on korkeintaan 23 paikan päässä omasta nimilapustaan. Koska ritareita on 24, on vähintään kahden ritarin oltava (jollakin) samalla etäisyydellä d omasta paikastaan. Siis jos pöytää kierretään d askelta, nämä vähintään kaksi ritaria saadaan omille paikoilleen.

24 ei ole tässä mikään taikaluku, sillä kyyhkyslakkaperiaate kyllä soveltuu muihinkin vastaavankaltaisiin tilanteisiin. 24 on vain valittu siksi, ettei kaikkien järjestysvaihtoehtojen läpikäynti yksi kerrallaan olisi ihan liian helppoa, mutta toisaalta ei liian vaikeaakaan.

Kysyin alkuperäisen jutun kommenttiosiossa, onnistuuko kierto enää välttämättä, jos yksi ritari olisikin istunut oikealle paikalle. Näkemykseni mukaan tässä tapauksessa ainakaan kyyhkyslakkaperiaatetta ei voida soveltaa, sillä väärille paikoille istuneet 23 ritaria ovat nyt 1–23 paikan päässä oikealta paikaltaan. Luultavasti on mahdollista konstruoida tilanne, jossa kiertämällä ei saada kuin yksi ritari kerrallaan paikalleen. En tosin ole nyt ihan varma. Todistakaapa tämä joko todeksi tai epätodeksi.

Muokattu 29.9.2015 – Neuvokas lukijamme Antti S. esittää alla mainion todistuksen sille, että homma onnistuu, vaikka yksi ritareista istuisikin aluksi epähuomiossa omalle paikalleen.