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.

1

Viiniä kuninkaan juhliin – ratkaisu

Kuninkaalla oli suuret syntymäpäiväjuhlat tulossa. Hän oli varannut juhlia varten 1000 tynnyrillistä viiniä kellariinsa. Mutta viikkoa ennen juhlia alkoi hovissa levitä huhu, että yksi tynnyreistä olisi myrkytetty. – – Kuningas päättää testata viinikellarinsa ministereillään. Mikä on vähin määrä ministereitä, joka kuninkaan on uhrattava, jotta hän varmasti saisi selville, mikä tynnyreistä on myrkytetty?

Kuten aiemmassa ongelmassa mainittiin, on binääriluvuilla lukuisia sovelluksia. Myös tämä ongelma ratkeaa lukujen muuttamisella binäärijärjestelmään. Kertauksen vuoksi: luvun binääriesityksellä tarkoitetaan luvun esittämistä kakkosen potenssien avulla. Näin siis esimerkiksi 13=1\cdot 2^3+1\cdot 2^2+0\cdot 2^1+1\cdot 2^0=1101_2. Koska 2^9=512 ja 2^{10}=1024, ongelma voidaan ratkaista vähimmillään kymmenen ministerin avustuksella.

Liitetään jokaiseen tynnyriin yksilöllinen 10-bittinen binääriluku; lisätään tarvittaessa luvun eteen nollia. Esimerkiksi 6. tynnyri olisi 0000000110 ja 789. tynnyri 1100010101. Tämän jälkeen järjestetään ministerit järjestykseen ensimmäisestä kymmenenteen. Tynnyrin binääriluvun bitti (1 tai 0) kertoo, pitääkö kunkin ministerin maistaa tynnyristä vai ei. Tässä esimerkiksi ensimmäinen ja toinen ministeri eivät maistaisi 6. tynnyristä, mutta maistaisivat 789. tynnyristä. Kolmannen ministerin ei tarvitsisi maistaa kummastakaan, kun taas esimerkiksi tynnyristä numero 245 (eli binäärisenä 0011110101) hän maistaisi, kuten myös neljäs, viides, kuudes, kahdeksas ja kymmenes ministeri.

0

Rahojen punnitus – ratkaisu

Kahdestatoista samannäköisestä rahasta yksi on väärennetty. Se on joko hieman liian kevyt tai liian painava. Käytettävissä on tasapainovaaka. Mikä on vähin määrä punnituksia, jolla voit varmasti selvittää, mikä rahoista on väärä ja onko se liian kevyt vai liian painava?

Tarvittavien punnitusten määrä on kolme. Aloitetaan punnitsemalla molemmissa vaakakupeissa neljä kolikkoa. Jos punnitus on tasapainossa, on virheellinen kolikko neljän jäljelle jääneen joukossa. Näistä punnitaan kolme toisessa kupissa ja kolme oikeaa kolikkoa toisessa. Jos tämäkin on tasapainossa, on virheellinen kolikko löytynyt, ja kolmas punnitus osoittaa, onko se liian kevyt vai liian painava.

Jos taas kolme ”väärää” ja kolme oikeaa tuottaa epätasapainon, on löydetty se, onko haettu kolikko liian painava vai liian kevyt. Tämän jälkeen virheellinen yksilö löytyy laittamalla kolmesta mahdollisesta väärästä yksi kumpaankin vaakakuppiin. Tasapaino kertoo, että se kolmas on väärä, epätasapaino puolestaan sen, kumpi punnituista on väärän painoinen.

Tilanne muuttuu hankalammaksi, kun ensimmäinen 4+4-punnitus osoittaa epätasapainoa. Tämän jälkeen meillä on neljä ”painavaa”, neljä ”kevyttä” ja neljä varmasti oikeaa kolikkoa. Jatketaan nyt laittamalla kolme painavaa ja yksi kevyt toiseen kuppiin sekä yksi painava ja kolme oikeaa toiseen kuppiin. Mahdollisia tapauksia on nyt kolme.

Ensinnä, jos punnitus antaa tasapainon, on etsitty kolikko kolmen punnitsemattoman kevyen joukossa, joista se saadaan esille punnitsemalla yksi kolikko molemmissa kupeissa. Samaan tapaan virheellinen kolikko löytyy, mikäli punnitus osoittaa kolmen painavan kolikon puolen olevan edelleen painavampi.

Kolmas tapaus puolestaan on se, jos kolmen painavan kolikon puoli onkin nyt kevyempi. Tällöin joko yksinäinen painava kolikko on painavampi tai yksinäinen kevyt on kevyempi. Laittamalla kolmannessa punnituksessa nämä kaksi toiseen kuppiin ja kaksi oikeaa toiseen kuppiin ratkeaa epätasapainon suunnasta, kummasta kolikosta oli kyse.

Näin. Pirullinen ongelma sinänsä sangen yksinkertaisen tuntuisesta lähtötilanteesta.

0

Venäläisen talonpojan kertolasku – ratkaisu

Otetaan esimerkiksi vaikkapa tulo 117\cdot 324. Homma toimii seuraavasti: jaetaan toista luvuista toistuvasti kakkosella. Jakojäännöksestä ei tarvitse välittää, vain kokonaiset lasketaan. Näin edetään, kunnes ollaan päästy ykköseen. Viereiseen sarakkeeseen aletaan puolestaan kertoa toista luvuista toistuvasti kakkosella. Kun ollaan päästy yhtä pitkälle kuin vasemmalla, vedetään yli kaikki ne luvut, jotka vastaavat parillista lukua vasemmanpuoleisessa sarakkeessa. Jäljelle jäävät luvut lasketaan yhteen, ja halutun tulon arvo on saatu. Kysymys kuuluu, miksi tämä menetelmä toimii mille tahansa kokonaislukujen tulolle.

Venäläisen talonpojan kertolaskun taustalla on lukujen binääriesitys. Binäärijärjestelmä toimii aivan kuten meille tuttu kymmenjärjestelmäkin, mutta kymmenen sijaan kantalukuna on luku 2. Kun siis esimerkiksi

    \[17034=1\cdot 10^4+7\cdot 10^3+0\cdot 10^2+3\cdot 10^1+4\cdot 10^0,\]

on binääriesityksessä käytettävissä vain numerot 0 ja 1. Siis vaikkapa 23 on binäärilukuna 10111, koska

    \[23=16+4+2+1=1\cdot 2^4 + 0\cdot 2^3+1\cdot 2^2+1\cdot2^1+1\cdot 2^0.\]

Näyttökuva 2015-8-29 kello 20.37.00

Miten tämä sitten liittyy venäläisen talonpojan kertolaskuun? Ideana on muodostaa toisen tulontekijän binääriesitys ja kertoa sillä tulon toista tekijää. Binääriesityksen muodostaminen luvulle on helppoa. Jaetaan luku ensin toistuvasti kakkosella, kunnes jäljellä on vain ykkönen. Luetaan binääriesitys alhaalta ylöspäin. Jos jaon tulos on ollut pariton (eli jakojäännös on jäänyt), on tarvittava bitti 1, jos taas jako on parillinen, bitiksi valitaan 0. Näin voidaan selvästi toimia riippumatta siitä, mikä kokonaisluku on kyseessä.

Näin toimien huomaame luvun 117 binääriesityksen olevan 1110101, sillä 

    \[117=1\cdot 2^6+1\cdot 2^5+1\cdot 2^4+0\cdot 2^3+1\cdot 2^2+0\cdot 2^1+1\cdot 2^0.\]

Nyt laskemamme laskutoimitus onkin periaatteessa 324\cdot (2^0+2^2+2^4+2^5+2^6) eli

    \[324+324\cdot 4+324\cdot 16+ 324\cdot 32+324\cdot 64,\]

joka tietenkin on oikeanpuoleisten yliviivaamattomien lukujen summa. Hauskaa ja melko helppoa, eikö?

Binääriluvuilla on lukematon määrä sovelluksia. Jos mainitsen niistä yhden, voi kukin päätellä niitä jokusen lisää. Nimittäin kaikki maailman tietokoneet perustuvat binäärijärjestelmään.

0

200 kalan akvaario – ratkaisu

Akvaariossa on 200 kalaa, joista 198 on kultakaloja. Kuinka monta kultakalaa akvaariosta pitää poistaa, jotta niiden suhteellinen osuus laskisi 99 prosentista 98 prosenttiin?

Olkoon poistettavien kalojen lukumäärä x. Saadaan yhtälö

    \[\frac{198-x}{200-x}=0,99.\]

Tästä saadaan, että x=100. Kultakaloja pitää siis poistaa sata.

0

Kaksi jokilaivaa – ratkaisu

Kaksi jokilaivaa lähtee samaan aikaan joen vastakkaisilta rannoilta tasaisella nopeudella suoraviivaisesti kohti vastarantaa; toinen laivoista on nopeampi. Kun laivat kohtaavat, on lähempi ranta 720 metrin päässä. Molemmat laivat pysähtyvät rannalle kymmeneksi minuutiksi, ja kun ne kohtaavat seuraavan kerran, ovat ne 400 metrin päässä toisesta rannasta. Kuinka leveä joki on?Kaksi jokilaivaa

Olkoon joen leveys x metriä. Kumpikin laiva pysähtyy kymmeneksi minuutiksi, joten tällä ei ole merkitystä ratkaisun kannalta. Voidaan keskittyä pelkästään joella kulutettuun aikaan. Koska laivat kulkevat tasaisella nopeudella, ovat kuljettu matka ja käytetty aika suoraan verrannolliset. Tämä johtaa pariin melko yksinkertaiseen ratkaisumalliin.

Ensinnäkin, kun laivat kohtaavat ensimmäisen kerran, ovat ne taittaneet matkaa yhteensä x metriä. Toisen kohtaamisen hetkellä matkaa on taitettu puolestaan 3x metriä (molemmat laivat kertaallen koko välin ja vajaan toisen välin), joten kulutettu aikakin on kolminkertainen. Nopeamman laivan kulkemaa matkaa tutkimalla tästä saadaan yhtälö

    \[3(x-720)=2x-400,\]

jonka ratkaisu x=1760 (metriä) on joen leveys.

Toisaalta matkan ja käytetyn ajan verrannollisuus johtaa myös laivojen kulkemista matkoista laadittuun verrantoyhtälöön 

    \[\frac{x-720}{720}=\frac{2x-400}{x+400},\]

 josta nimittäjät pois kertomalla ja termejä järjestelemällä saadaan x^2-1760x=0. Tämän yhtälön positiivinen juuri on tietenkin sama x=1760.

0

Kärpänen – ratkaisu

Auto ajaa 60 km/h. Sitä vastaan lähtee 100 kilometrin päästä mopo, jonka nopeus on 40 km/h. Auton etupuskurilta lähtee samalla hetkellä lentoon kärpänen, joka lentää 80 km/h kohti mopoa. Kun kärpänen saavuttaa mopon, se lähtee takaisin kohti autoa, jonka luona se kääntyy välittömästi kohti mopoa ja niin edelleen. Kuinka pitkän matkan kärpänen ehtii lentää ennen kuin auto ja mopo kohtaavat?

Auto ja mopo kohtaavat tunnin kuluttua lähdöstä. Siis kärpänen lentää 80 kilometriä. Kuten eräs vakiokommentaattori Twitterissä totesi, kannattaisi ehkä uskoa vähitellen #viikonhelppo-tunnistetta. Toki tämän ongelman voi ehkä ratkoa jollakin hankalammallakin tavalla…

Niin, ja ilmeisesti ongelmassa hämäsi myös sen epäluonnollisuus. Minulle valistettiin, että kärpäsen lentonopeus on oikeastaan noin 8 km/h. Mutta tämä olikin matemaattinen erikoiskärpänen. Pistemäinen, ja niin edelleen.

0

Kuution sahaus – ratkaisu

Kuutio voidaan jakaa kuudella suoralla sahauksella 27 tasakokoiseksi pieneksi kuutioksi. Jos yksittäisen sahauksen jälkeen kuution osia voisi mielensä mukaan järjestellä uudelleen, olisiko mahdollista vähentää tarvittavien sahauksien määrää?

Sahauksien lukumäärää ei voi vähentää kuudesta. Keskimmäisessä kuutiossa on kuusi sahattavaa pintaa.

0

Pyöräilijän ja autoilijan kohtaus – ratkaisu

Pyöräilijä lähtee Tampereelta kohti Varkautta polkien tasaisella nopeudella. Tuntia myöhemmin Varkaudesta lähtee autoilija niin ikään tasaisella nopeudella kohti Tamperetta. Kun he kohtaavat, kumpi on lähempänä Tamperetta?

Tämä arvoitus herätti hieman hämmentynyttä vastakaikua, joten lienee tarpeen selventää, että kyseessä on tietenkin huumori. Me matemaatikot olemme hauskoja! Keksimme sellaisiakin vitsejä, että olkoon \epsilon < 0

Vastaus on siis, että yhtä kaukanahan he Tampereelta ovat, kun he kohtaavat. Tässä siis oletetaan, että autoilija ja pyöräilijä ovat pistemäisiä, täsmälleen samalla reitillä kulkevia objekteja.

Tämä vitsi tuo mieleeni yhden toisen ongelman, joka löytyy lukiomatematiikan oppikirjoistakin. Ja tämän toisen ongelman ratkaisu on hieno, vaikkei ehkä samaan tapaan humoristinen. Tämä on ihan oikeasti matematiikkaa.

Siis: Retkeilijä lähtee tunturihotellilta kello 7 aamulla kohti autiotupaa, jossa hän on perillä kello 17 illalla. Seuraavana päivänä hän lähtee takaisin kohti tunturihotellia samaa reittiä kulkien kello 9 aamulla ollen perillä kello 15. Osoita, että hän voi molempina päivinä pitää evästauon täsmälleen samassa kohdassa täsmälleen samaan aikaan.

0

Kuinka monta rationaalilukua on – ratkaisu

Näyttää siltä, että luonnollisia lukuja on tuplasti enemmän kuin parillisia luonnollisia lukuja, mutta itse asiassa onkin niin, että niitä on ”yhtä äärettömästi”. Mikä olisi kätevä tapa osoittaa tämä?

Rationaaliluvut ovat tiheitä reaalilukujen joukossa, eli kun valitaan mitkä tahansa kaksi reaalilukua, niin niiden väliin mahtuu aina rationaaliluku. Tämä ominaisuus ei selvästikään ole esimerkiksi luonnollisilla luvuilla voimassa. Mutta voitaisiinko silti osoittaa, että rationaalilukuja on ”yhtä äärettömästi” kuin luonnollisia lukuja?

Toimiva ratkaisu joukkojen osoittamiseksi yhtä mahtaviksi (eli joukoiksi, joissa on yhtä monta alkiota) on näyttää, että joukkojen välille voidaan muodostaa niin kutsuttu bijektio. Tämä tarkoittaa sitä, että joukkojen alkioiden välille voidaan muodostaa 1–1-vastaavuus. Hieman toisin tulkittuna kyse on siis funktion ja sen käänteisfunktion olemassaolosta tarkasteltavien joukkojen välillä.

Luonnollisten lukujen ja parillisten luonnollisten lukujen välille 1–1-vastaavuuden löytäminen on yksinkertaista:

    \[\begin{array}{ccccccccc} 0&1&2&3&4&5&6&7&\ldots\\ \updownarrow&\updownarrow&\updownarrow&\updownarrow&\updownarrow&\updownarrow&\updownarrow&\updownarrow&\\ 0&2&4&6&8&10&12&14&\ldots \end{array}\]

Samaa ideaa voidaan välittömästi laajentaa myös muihin joukkoihin. Esimerkiksi kokonaislukujen ja luonnollisten lukujen joukot ovat selvästi yhtä mahtavia.

Miten sitten osoitetaan rationaaliluvut yhtä mahtavaksi joukoksi luonnollisten lukujen kanssa? Yksi tunnettu menetelmä on seuraavassa. Tutkitaan ensin positiivisten kokonaislukujen ja positiivisten rationaalilukujen yhteyttä. Muodostetaan positiivisista kokonaisluvuista oheinen taulukko.

    \[\begin{array}{c|cccccccc} &1&2&3&4&5&6&7&\ldots\\ \hline 1&\frac{1}{1}&\frac{1}{2}&\frac{1}{3}&\frac{1}{4}&\frac{1}{5}&\frac{1}{6}&\frac{1}{7}&\ldots\\ 2&\frac{2}{1}&\frac{2}{2}&\frac{2}{3}&\frac{2}{4}&\frac{2}{5}&\frac{2}{6}&\frac{2}{7}&\ldots\\ 3&\frac{3}{1}&\frac{3}{2}&\frac{3}{3}&\frac{3}{4}&\frac{3}{5}&\frac{3}{6}&\frac{3}{7}&\ldots\\ 4&\frac{4}{1}&\frac{4}{2}&\frac{4}{3}&\frac{4}{4}&\frac{4}{5}&\frac{4}{6}&\frac{4}{7}&\ldots\\ 5&\frac{5}{1}&\frac{5}{2}&\frac{5}{3}&\frac{5}{4}&\frac{5}{5}&\frac{5}{6}&\frac{5}{7}&\ldots\\ 6&\frac{6}{1}&\frac{6}{2}&\frac{6}{3}&\frac{6}{4}&\frac{6}{5}&\frac{6}{6}&\frac{6}{7}&\ldots\\ 7&\frac{7}{1}&\frac{7}{2}&\frac{7}{3}&\frac{7}{4}&\frac{7}{5}&\frac{7}{6}&\frac{7}{7}&\ldots\\ 8&\frac{8}{1}&\frac{8}{2}&\frac{8}{3}&\frac{8}{4}&\frac{8}{5}&\frac{8}{6}&\frac{8}{7}&\ldots\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\\ \end{array}\]

Aletaan nyt käydä tätä taulukkoa läpi järjestelmällisesti vasemmasta yläkulmasta alkaen aina diagonaali kerrallaan ja vaihdetaan aina reunalle päästyämme suuntaa. Hypätään yli kaikki ne rationaaliluvut, jotka eivät ole yksinkertaisimmassa mahdollisessa muodossa. Saadaan siis jono 1, 2, \frac{1}{2}, \frac{1}{3}, (hypätään yli \frac{2}{2}=1), 3, 4, \frac{3}{2}, \frac{2}{3}, \frac{1}{4}, \frac{1}{5}, (hypätään yli \frac{2}{4}, \frac{3}{3} ja \frac{4}{2}), 5, 6, \frac{5}{2} ja niin edelleen.

Näin jatkamalla tulee selvästi jokainen positiivinen rationaaliluku käydyksi läpi. Ja koska ne voidaan siis luetella järjestyksessä, on niiden ja positiivisten kokonaislukujen 1, 2, 3, 4, \ldots välillä ilmeinen 1–1-vastaavuus. Pienellä vaivalla myös nolla sekä negatiiviset rationaaliluvut saadaan otettua mukaan luetteloon. Siis rationaalilukuja on ”yhtä monta” kuin luonnollisia lukuja.

Eräs tämän ongelman kiehtovia variaatioita tunnetaan esittäjänsä David Hilbertin mukaan nimellä Hilbertin hotelli. Siihen voi tutustua vaikkapa tästä.