Pulmat

1

Loogiset lautapelaajat

|

Ystävykset Hannu, Mikko ja Tuomo pelaavat lautapeliä. Pystytkö selvittämään herrojen pelinappuloiden värit, kun tiedetään, että ne ovat punaiset, vihreät ja violetit, ja että seuraavista väittämistä täsmälleen yksi pitää paikkansa:

  • Hannu pelaa punaisilla.
  • Mikko ei pelaa punaisilla.
  • Tuomo ei pelaa violeteilla.
Kuva: Mikko Saari / Boardgamegeek (CC BY-NC-SA 3.0)

Kuva: Mikko Saari / Boardgamegeek (CC BY-NC-SA 3.0)

Tämä pulma taitaa olla yksi modernin lauselogiikan vanhimmista, ja sen on jossakin muodossa esittänyt jo logiikan ja tietokonearitmetiikan grand old man George Boole, jonka syntymästä tuli marraskuun 2015 alussa kuluneeksi 200 vuotta.

 

Ratkaisu: Erilaisia kolmen pelivärin yhdistelmiä on vain kuusi erilaista. Nämä kaikki läpikäymällä (mikä näin pienen aineiston yhteydessä yleensä on riittävän yksinkertainen ratkaisutapa) oikea väriyhdistelmä löytyy helposti.

Toisaalta pelkkä järkeilykin vie perille. Selvästikään Hannun väri ei voi olla punainen, sillä jos olisi, myös Mikkoa koskeva väite olisi totta. Jos taas Mikko ei pelaa punaisilla, Tuomon olisi pakko pelata violeteilla, tai muuten häntä koskeva väittämä pitäisi paikkansa. Tällöin Hannu saisi punaiset, mikä olisi mahdotonta, koska myös näin tulisi kaksi totta väitettä. Siis on oltava niin, että Tuomo ei pelaa violeteilla on totta. Tällöin Mikko pelaa punaisilla ja Hannu ei, ja koska Tuomo ei pelaa violeteilla, on violetti Hannun ja vihreä Tuomon väri.

(Kyllä, tässä pulmassa esiintyneille henkilöille oikeine peliväreineen saattaa löytyä jonkinlaisia vastineita tosielämässä.)

1

Peräkkäisten kokonaislukujen summa

|

Tämänkertainen pulmamme on kaksiosainen – viikon helppo ja viikon vaikea samassa paketissa. Löysin tämän lukuteoreettisen ongelman standup-matemaatikkona esiintyvän Matt Parkerin ensiluokkaisesta kirjasta Things To Make And Do In Fourth Dimension, ja se kuuluu seuraavasti.

Etsi lukujen 10 ja 20 väliltä ainoa kokonaisluku, jota ei voida esittää kahden tai useamman peräkkäisen positiivisen kokonaisluvun summana. Kun olet löytänyt sen, etsi sellainen (ainoa lajiaan, muuten) lukujen 30 ja 40 väliltä. Entä löydätkö lukujen 20 ja 30 väliltä tällaisia lukuja? Tässä lienee riittävästi purtavaa viikon helpon pulman tarpeisiin.

Vaikeampi pulma on tietenkin löytää kaikki sellaiset positiiviset kokonaisluvut, joita ei voida esittää peräkkäisten positiivisten lukujen summana. Entä miten tämä voidaan osoittaa?

Ratkaisu: Lukujen 10 ja 20 väliltä ainoa luku, jota ei voida esittää kahden tai useamman peräkkäisen luvun summana on 16. Lukujen 30 ja 40 väliltä löytyy tällaisista luvuista luku 32. Lukujen 20 ja 30 välillä ei tällaisia lukuja ole. Onko tässä vinkkiä tarpeeksi? Kyllä vain: kaikki muut luvut voidaan esittää peräkkäisten lukujen summina paitsi kakkosen potenssit. Todistetaan tämä:

Aloitetaan yksinkertaisesti. Kaikki parittomat luvut voidaan esittää muodossa 2n+1, missä n on jokin kokonaisluku. Tämä tarkoittaa heti sitä, että pariton luku voidaan ilmoittaa muodossa n+(n+1), eli kahden peräkkäisen luvun summana.

Siirrytään sitten parillisiin lukuihin. Jos luku on jaollinen kolmella, se voidaan ilmoittaa muodossa 3n, missä n on kokonaisluku. Toisaalta

    \[3n=(n-1)+n+(n+1),\]

joten kaikki kolmella jaolliset luvut voidaan esittää kolmen peräkkäisen luvun summana. Itse asiassa on helppo huomata, että

    \[5n=(n-2)+(n-1)+n+(n+1)+(n+2),\]

ja että sama idea yleistyy välittömästi kaikille muillekin parittomalla luvulla jaollisille kokonaisluvuille. Näin on saatu katettua jo kaikki muut luvut paitsi kakkosen potenssit (sillä kaikissa muissa parillisissa luvuissa on jokin pariton luku tekijänä). Nyt on osoitettava enää, että mitään kakkosen potensseja ei todellakaan voida kirjoittaa peräkkäisten lukujen summaksi.

Tutkitaan yleisesti k peräkkäisen kokonaisluvun summaa. Jos lukuja on pariton määrä, on summa jaollinen jollakin parittomalla luvulla, kuten edellä todettiin. Tutkitaan siis yleistä peräkkäisten lukujen summaa, jossa on parillinen määrä summan tekijöitä. Jos ensimmäinen luvuista on m, on viimeinen niistä m+(k-1). Saadaan aritmeettinen summa

    \[m+(m+1)+(m+2)+\cdots +(m+(k-1))\]

    \[=km+(0+1+2+\cdots +(k-1))\]

    \[=km+\frac{k}{2}(k-1).\]

Lavennetaan ensimmäistä termiä kakkosella ja otetaan osoittajasta k yhteiseksi tekijäksi. Saadaan

    \[km+\frac{k}{2}(k-1)=\frac{k(2m-k-1)}{2}.\]

Koska k on parillinen kokonaisluku, on tulon tekijä (2m-k-1) varmasti pariton, joten saatu luku ei voi olla kakkosen potenssi. Näin ollen kakkosen potensseja ei voida milloinkaan esittää peräkkäisten lukujen summana.

0

Neliön kolmijako

|

Neliön yhdestä kärjestä vedetään kaksi kuvan mukaista janaa, jotka jakavat neliön kolmeen yhtä suureen osaan. Missä suhteessa janat jakavat neliön sivut?Näyttökuva 2015-11-5 kello 19.25.34

 

Ratkaisu: Sivujen jakosuhde on 2:1. Tämä on helppo huomata esimerkiksi piirtämällä neliölle lävistäjä samasta kärjestä, josta janat lähtevät. Nyt muodostuvien symmetristen kolmioiden alojen suhteen on selvästi oltava 2:1, jotta alkuperäisten janojen erottama nelikulmio olisi kolmannes koko neliön alasta. Koska kolmioilla on sama korkeusjana (neliön sivu), on alojen suhde välttämättä kannan jakosuhde.

Näyttökuva 2015-11-5 kello 19.27.07

0

Venäläisen kolmion piiri

|

Ystäväni Tuomas Salo törmäsi Moskovan-vierailullaan viime vuosituhannen lopulla seuraavaan oivallisen kauniiseen pulmaan.

Valitaan mielivaltaisesti piste A positiiviselta x-akselilta väliltä ]0,1[ ja piste B positiiviselta y-akselilta väliltä ]0,1[. Valitaan piste C mistä tahansa origokeskisen yksikköympyrän kehältä koordinaatiston ensimmäisestä neljänneksestä. Osoita, että kolmion ABC piiri on enemmän kuin 2.

Ellet muuten usko, voit liikutella pisteitä oheisessa Geogebra-appletissa. Jos appletti ei näy tässä, voit leikkiä sillä Geogebratubessakin.

 

Ratkaisu: Tämän ongelman voinee ratkaista algebrallakin – Pythagoraan lausetta ja muutamia luotaantyöntäviä yhtälöitä ja niin edelleen. Seuraava ratkaisu on kuitenkin kauneudessaan ilmiömäinen ja, mikä tärkeintä, täysin riittävä.venalainenongelma

Peilataan piste C x– ja y-akseleiden suhteen pisteiksi C' ja C''.Nyt symmetrian nojalla janat AC ja AC' ovat keskenään yhtä pitkät, samoin janat BC ja BC''. Näin ollen kolmion ABC piiri on sama kuin murtoviivan C'ABC'' pituus. Koska C'C'' on ympyrän halkaisija, ja siis pituudeltaan 2, on kysytty piiri selvästi tätä pidempi.

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

0

Muurahaisen helppo 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 täsmälleen kolme särmää kuljettuaan?

Ratkaisu: Jokaisessa kärjessä muurahaisella on kolme vaihtoehtoa seuraavalle suunnalle, joten erilaisia kolmen särmän reittejä on tuloperiaatteen mukaan 3\cdot 3\cdot 3=27.

Mietitään sitten, kuinka moni reiteistä vie kolmea särmää pitkin kärkeen B. Kärki A on ainoa kärki, josta etäisyys kärkeen B on 3 särmää. Kustakin kärjestä, johon kärjestä A pääsee, etäisyys on 2 särmää. On samantekevää, mikä suunta valitaan ensin – sopivia vaihtoehtoja on siis 3. Toisessa kärjessä on aivan sama, minne muurahainen jatkaa matkaansa, kunhan se ei palaa takaisin. Vaihtoehtoja on siis 2. Kolmannesta kärjestä on yksi reitti kärkeen B. Näin ollen suotuisia reittejä on 3\cdot 2\cdot 1=6.

Klassisen todennäköisyyden mukaan kysytty todennäköisyys on siis \frac{6}{27}=\frac{2}{9}.

No niin, tämä oli helppo. Nyt mars mars Muurahaisen vaikean juoksun pariin. Eiköhän tästä ainakin yksi tai kaksi vihjettä sen ratkaisemiseksi tullut.

6

Kaksi rahakuorta

|

Tämä ongelma liittyy oleellisesti kolmen rahakuoren pulmaan, joten suosittelen tutustumaan siihen ja sen ratkaisuun ensin. Luvassa on ensinäkemältä hämmästyttävä paradoksi.

Saat kirjekuoren, jossa on tietty määrä rahaa. Minulla on suljettu kirjekuori, jossa on joko kaksi kertaa enemmän rahaa kuin sinun kuoressasi tai vain puolet rahoistasi. Kannattaako sinun vaihtaa?

Päätellään kuten kolmen kuoren ongelmassa, että vaihtaminen kannattaa:

  1. Olkoon kuoressasi X euroa.
  2. Rahasumma X voi olla joko suurempi tai pienempi kuin toisen kuoren rahasumma.
  3. Toisen kuoren rahasumma on siis \frac{X}{2} todennäköisyydellä \frac{1}{2} tai 2X todennäköisyydellä \frac{1}{2}.
  4. Näin ollen rahasumman odotusarvoksi saadaan \frac{1}{2}\cdot \frac{X}{2}+\frac{1}{2}\cdot 2X=\frac{5}{4}X.

Uskomaton tulos! Tämä sotii vahvasti arkista järkeilyä vastaan. Onko vika päättelyssä vai arkijärjessä?

Ratkaisu: Tällä kerralla ongelma todella on päättelyssä, tarkemmin sanottuna kohdassa 3. Emme voi lähteä siitä, että toisessa kuoressa olisi 2X tai \frac{1}{2}X ja laskea odotusarvoa kuten kolmen kuoren ongelmassa. Tämä siksi, että ne molemmat eivät ole mahdollisia tapauksia.

Oikeaa päättelyä olisi todeta, että on kaksi rahakuorta, joissa on rahasummat X ja 2X, mutta emme tiedä, kumpi niistä on hallussamme. Nyt hallussamme olevan rahasumman odotusarvo on \frac{1}{2}\cdot X+\frac{1}{2}\cdot 2X=\frac{3}{2}X, mikä puolestaan tarkoittaa, että on yhdentekevää, vaihtaako vai ei. On yhtä todennäköistä, että hallussa on iso tai pieni rahasumma, eikä se vaihtamalla muutu.

Tämänkin pulman lähteenä oli Thomas Poveyn matematiikka- ja fysiikkaongelmia käsittelevä opus Professor Povey’s Perplexing Problems.

2

Kolme rahakuorta

|

Seuraava pulma on jälleen Thomas Poveyn peruja. Se on sukua kuuluisalle Monty Hallin ongelmalle, mutta siinä on oma pieni lisämausteensa.

Saat kirjekuoren, jossa on tietty summa rahaa. Tämän jälkeen näytän sinulle kaksi muuta kuorta, joista toisessa on kaksinkertainen rahasumma ja toisessa puolet kirjekuoresi rahasummasta. Suljen kaksi muuta kuorta ja sekoitan ne niin, ettei niistä voi mitenkään päätellä, kumpi oli kumpi. Nyt sinulla on kaksi vaihtoehtoa: voit joko pitää nykyisen kuoresi tai vaihtaa jompaan kumpaan toisista kuorista. Mitä sinun kannattaisi tehdä?

Ratkaisu: Tutkitaan ongelmaa odotusarvon käsitteen kautta. Odotusarvo tarkoittaa eräänlaista satunnaisilmiön jakauman keskiarvoa, jota laskettaessa satunnaismuuttujan arvot painottuvat niiden todennäköisyyksien suhteessa.

Olkoon nyt kirjekuoressasi oleva rahasumma X. Näin ollen kahdessa muussa kuoressa olevat rahasummat ovat 2X sekä \frac{1}{2}X. Nyt on kaksi mahdollista tapausta.

  1. Et vaihda kuoria. Tällöin saamasi rahasumman odotusarvo on varmasti X.
  2. Vaihdat. Nyt voit todennäköisyydellä \frac{1}{2} saada kuoren, jossa on 2X, ja samoin todennäköisyydellä \frac{1}{2} kuoren, jossa on \frac{1}{2}X. Saamasi rahasumman odotusarvo on nyt \frac{1}{2}\cdot 2X+\frac{1}{2}\cdot\frac{1}{2}X=\frac{5}{4}X.

Näin ollen vaihto kannattaa.

 

0

Kaarien rajaama ala

|

Sain viimein käsiini Thomas Poveyn pulmakirjan nimeltä Professor Povey’s Perplexing Problems (Oneworld Publications, 2015). Jo nopealla ensi silmäilyllä ja todella pintapuolisella selailulla kävi selväksi, että nyt on käsissä helmi. Poveyn mukaan kirjan ongelmat eivät vaadi mitään lukiotason matematiikkaa kummempia menetelmiä, mutta luovaa kykyä ongelmanratkaisuun kyllä kaivataan. Tässä yksi maistiainen kirjan sisällöstä. Näyttää ihan helpolta, mutta –

Neliön sivun pituus on 2a. Sen vastakkaisista kärjistä piirretään ympyränkaaret, joiden säteet ovat a ja 2a. Mikä on kaarien rajaaman alueen pinta-ala?Näyttökuva 2015-10-9 kello 18.39.21

 

 

2

Laskut sekaisin

|

Kiireinen yrittäjä lähettää kuudelle asiakkaalleen laskun ja sulkee ne kirjekuoriin. Äkkiä hän huomaa, että osoitetarrat unohtuivat kuorien päältä. Millä todennäköisyydellä hän saa sattumanvaraisesti lätkimistään tarroista täsmälleen viisi oikeisiin kuoriin?

Kirjuri Ezra (n. 700-l.) Kuvalähde: Wikimedia Commons/Public domain

Kirjuri Ezra (n. 700-l.) Kuvalähde: Wikimedia Commons/Public domain

Ratkaisu: Todennäköisyys on nolla. Jos viisi osoitetta menee oikein, myös kuudes menee.