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

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

Potenssiyhtälö

Ratkaise yhtälö

    \[(x^2-7x+11)^{x^2-11x+30}=1.\]


Ratkaisu: Yhtälö ratkeaa kolmella eri ehdolla:

  1. x^2-7x+11=1. Tämän yhtälön ratkaisut ovat x=2 ja x=5.
  2. x^2-11x+30=0. Tämän ratkaisut ovat x=5 ja x=6. Lisäehtona on, että kantaluvun x^2-7x+11 on poikettava nollasta. Kumpikin ratkaisuista totetuttaa tämän vaatimuksen.
  3. x^2-7x+11=-1 ja x^2-11x+30 on parillinen. Nämä ehdot toteutuvat, kun x=3 tai x=4.

Yhtälön ratkaisut ovat siis x=2, x=3, x=4, x=5 ja x=6.

0

Pillinvääntöä

Taitetaan mehupilli kahdesta sattumanvaraisesta kohdasta. Millä todennäköisyydellä taitoksista saadaan kolmio?

Kuva: Petter Duvander/Flickr (CC BY-NC 2.0)


Ratkaisu: Kolmioepäyhtälön mukaan kolmio syntyy, mikäli yksikään paloista ei ole pidempi kuin kahden muun summa. Jos sovitaan, että pillin pituus on 1, tämä tarkoittaa sitä, että kunkin kolmesta osasta pitää olla lyhyempi kuin \frac{1}{2}.

Sovitaan, että taitoskohdat ovat x ja y, missä 0<x<1 ja 0<y<1. Kolmio muodostuu jommalla kummalla seuraavista ehdoista:

  1. x<y; x<\frac{1}{2}; y-x<\frac{1}{2}; 1-y<\frac{1}{2} tai
  2. y<x; y<\frac{1}{2}; x-y<\frac{1}{2}; 1-x<\frac{1}{2}.

Oheisessa kuvassa on ensimmäisen ehdon ratkaisualue on sinertävänä ja jälkimmäisen ehdon ratkaisualue vaaleanpunaisena. Kumpikin näistä on kooltaan \frac{1}{8} koko neliöstä, joten kolmio muodostuu todennäköisyydellä \frac{1}{4}.

Tämän pulman lähde on Matthew Scroggsin pulmasivu.

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

Neliöiden naapurit

 

Nyt on vuorossa perusgeometriaa! Oheisessa kuvassa ABCD ja AEFG ovat neliöitä. Osoita, että kolmioilla AGB ja ADE on sama pinta-ala.

Tämä pulma on Daniel Grillerin kirjasta Elastic Numbers. Löysin siihen helpon, mutta melko tylsän ratkaisun, joka on perusteltavissa lukiogeometrialla. Grillerin oma ratkaisu puolestaan on oleellisesti yksinkertaisempi ja kauniimpi. Sen ymmärtää alakoululainenkin! Siksipä tässä on sangen nätti viikon helppo pulma.


Kuva 1: Suplementtikulmat

Ratkaisu: Oma ideani perustui siihen, että koska kulmat BAD ja EAG ovat suoria, ovat kulmat \alpha ja \beta ovat suplementtikulmia, eli ne muodostavat yhdessä 180^{\circ} kulman (kuva 1). Lukiotrigonometriassa opimme rakkaan työkalumme yksikköympyrän avulla, että kulmalla ja sen suplementtikulmalla on sama sini. Ja koska kolmion ABG ala voidaan laskea kaavalla \displaystyle\frac{1}{2}ab\sin \alpha, missä a ja b ovat kulman \alpha kyljet, ja yhtä lailla kolmion ADE ala on \displaystyle\frac{1}{2}ab\sin \beta, niin selvästi kolmioiden alat ovat samat.

Joo, ei hirveän tyylikäs ratkaisu, mutta ratkaisu kuitenkin, ja itse tuloshan on varsin mukava.

Kuva 2: Kierto pisteen A ympäri

Daniel Griller lähtee myös samasta ajatuksesta: \alpha+\beta=180^{\circ}. Mutta hän vie idean nokkelasti pidemmälle (Kuva 2). Koska AB=AD=a, voidaan kolmio AGB kiertää 90 astetta pisteen A ympäri kolmioksi AHD, jossa AH=AG=b ja \gamma=\alpha (ja siis samalla \gamma+\beta=180^{\circ}, joten pisteet A, E ja H ovat samalla suoralla). Nyt meillä on kaksi kolmiota, AHD ja AED, joilla on sama kanta b ja sama korkeus, mistä ratkaisu välittömästi seuraa.

0

Istumapaikka

Kuva: Rob Stanley/Flickr (CC BY-NC 2.0)

Mikko istuu suuressa loppuunmyydyssä suorakulmion muotoisessa katsomossa1. Hänen edessään olevilla riveillä istuu 175 henkeä ja takanaan olevilla riveillä 400 henkeä. Sarakkeissa Mikon vasemmalla puolella istuu 312 henkeä ja oikealla puolella 264 henkeä. Monennenko rivin monennellako paikalla Mikko istuu?


Ratkaisu: Pulman ratkaisu piilee jaollisuudessa. Aloitetaan tutkimalla Mikon edessä olevia 175 paikkaa. Nyt luvun 175 alkutekijähajotelma on 175=5^2\cdot 7, joten järkeviä mahdollisuuksia Mikon eteen ovat vain 7 riviä, joilla on 25 paikkaa kullakin, tai 5 riviä, joilla on 35 paikkaa, tai toisinpäin.

Mikon takana tilanne on hieman monimutkaisempi: alkutekijähajotelmaksi saadaan 400=2^4\cdot 5^2, mutta koska 35 ei ole luvun 400 tekijä, jää parhaaksi vaihtoehdoksi, että Mikon takana olisi 16\cdot 25 paikkaa.

Tarkastellaan sitten sivuja. Nyt 312=2^3\cdot 3\cdot 13 ja 264=2^3\cdot 3\cdot 11. Näistä hyvät paikkamääräkombinaatiot ovat 13\cdot 24=312 ja 11\cdot 24=264.

Yhdessä näistä voidaan päätellä, että salissa pitäisi olla 24 riviä ja 25 saraketta, ja edelleen Mikon paikka on 8. rivillä, 14. sarakkeessa.

Voidaan myös helposti huomata, että jos lasketaan Mikon edestä ja takaa löytyvät paikat yhteen, saadaan 175+400=575 paikkaa lukuunottamatta riviä, jolla Mikko istuu, ja sivuilta laskien 312+264=576 paikkaa lukuunottamatta saraketta, jossa Mikko istuu. Näin ollen sarakkeita on oltava yksi enemmän kuin rivejä.

Tämä pulma on peräisin Daniel Grillerin uudesta kirjasta Elastic Numbers, jota ovat suitsuttaneet ainakin Alex Bellos ja Matthew Scroggs – molemmat miehiä, joiden pulmasuosituksiin kannattaa tarttua. Niinpä kyseinen opus koristaakin työpöytääni toivottavasti jo tulevalla viikolla!

2

Parittomat tekijät

Tällä viikolla, kun koulujen kesälomat alkavat vedellä viimeisiään ja vettä sataa edelleen, on hyvä perehtyä yhteen Pulmakulman kaksivuotisen historian kauneimmista (jos kohta myös yhteen vaativimmista) pulmista.

Tekijöihinjako on yksi lukuteorian perusjuttuja. Tarkoitus on luetella, millä kaikilla luvuilla jokin kokonaisluku voidaan jakaa tasan. Yleensä rajoitutaan tutkimaan vain positiivisia lukuja. Esimerkiksi luvun 10 tekijät ovat 1, 2, 5 ja 10. Yksi tärkeimmistä lukuteorian lauseista on aritmetiikan peruslause, jonka mukaan mikä tahansa ykköstä suurempi kokonaisluku voidaan esittää alkulukujen tulona ja tämä esitys on tekijöiden järjestystä vaille yksikäsitteinen.

Ja nyt siihen viikon vaikeaan pulmaan.

Olkoon nyt n jokin positiivinen kokonaisluku. Tutkitaan lukuja n+1, n+2, \ldots , 2n. Osoita, että näiden lukujen suurimpien parittomien tekijöiden summa on n^2.


Ratkaisu: Kun tutkitaan pienten lukujen suurimpia parittomia tekijöitä, huomataan jotain mielenkiintoista. Esimerkiksi, kun n=3, ovat lukujen 4, 5 ja 6 suurimmat parittomat tekijät 1, 5 ja 3. Vastaavasti asettamalla n=4 huomataan, että lukujen 5, 6, 7 ja 8 suurimmat parittomat tekijät ovat 5, 3, 7 ja 1. Edelleen eteenpäin menemällä alkaa näyttää siltä, että lukujen n+1, n+2, \ldots , 2n suurimmat parittomat tekijät ovat aina eri lukuja. Ja näin todella onkin.

Aritmetiikan peruslauseen mukaan jokainen luku voidaan siis esittää yksikäsittesenä alkulukujen tulona. Tämä taas puolestaan tarkoittaa sitä, että jos kahdella luvulla on sama suurin pariton tekijä, voivat niiden alkutekijähajotelmat poiketa toisistaan vain parillisten tekijöiden osalta. Ja koska 2 on ainoa parillinen alkuluku, tarkoittaa tämä sitä, että jos kahdella eri luvulla on sama suurin pariton tekijä, on toinen niistä vähintään kaksinkertainen toiseen nähden. Tästä seuraa heti se, että millään kahdella luvuista n+1, n+2, \ldots , 2n ei voi olla samaa suurinta paritonta tekijää, sillä 2n ei ole yli kaksinkertainen lukuun n+1 verrattuna.

Edelleen lukujen n+1 ja 2n välillä on täsmälleen n lukua, joten erilaisia suurimpia parittomia tekijöitä täytyy olla n kappaletta. Näistä suurin on 2n-1, joten pienimmän on oltava 1, ja välttämättä kaikki muutkin parittomat luvut näiden väliltä ovat mukana. Näin saadaan aritmeettisena summana

    \[1+3+5+\cdots +2n-1=n\cdot\frac{1+(2n-1)}{2}=n^2.\]

Tämä oivallinen pulma tuli kesällä jossain internetin ihmemaassa vastaan, mutta tarkemmin tutustuin siihen Daniel Grillerin kautta. Kiitokset myös Alex Bellosille ja Matthew Scroggsille Grillerin hienon Elastic Numbers -pulmakirjan mainostamisesta!

0

Kolikkopeli

Kuva: Mark Seton/Flickr (CC BY-NC 2.0)

Tuomas ja Heikki pelaavat seuraavilla säännöillä kolikonheittopeliä. He heittävät (reilua, painottamatonta) kolikkoa, kunnes kolmella peräkkäisellä heitolla tulee joko heittosarja klaava-klaava-kruuna tai klaava-kruuna-kruuna. Tuomas voittaa ensimmäisessä ja Heikki jälkimmäisessä tapauksessa.

Millä todennäköisyydellä Tuomas voittaa pelin?


Kuva 1: Klaavaputki toimii Tuomaksen eduksi.

Ratkaisu: Tilannetta voidaan mallintaa monilla tavoilla. Tämäntyyppisissä ongelmissa tykkään itse yleensä lähteä piirtelemään tilannetta auki esimerkiksi puukaavion avulla. Merkitään kruunan heittämistä R:llä ja klaavan heittämistä L:llä. Koska kumpikin voittosarja alkaa klaavalla, voidaan olettaa, että ensimmäinen (relevantti) heitto on ollut klaava.

Jos toinenkin heitto on klaava, ollaan menossa kohti Tuomaksen voittoa (kuva 1). Nyt kruuna katkaisee pelin Tuomaksen eduksi, klaava jatkaa peliä, mutta pitää edelleen Tuomaksella ratkaisevan edun.

Kuva 2: Lisää Tuomaksen voittolinjoja.

Tuomaksen peli ei ole pelattu, vaikka seuraava heitto olisikin kruuna: yksi klaava lisää, ja tilanne palautuu olennaisesti samaksi kuin edellä (kuva 2).

Entäpä Heikin voittolinja tai voittolinjat? Mistä ne löytyvät? Heikki tarvitsee kaksi peräkkäistä kruunaa klaavan jälkeen. Jos saadan klaava, on Heikki aina kahden peräkkäisen onnistuneen heiton päässä voitosta. Tämä on ratkaiseva ero Tuomaksen hyväksi, sillä Tuomaksella voitto voi olla jo yhden heiton päässä. Kaikki sarjat, jossa kaksi klaavaa esiintyy peräkkäin johtavat lopulta Tuomaksen voittoon. Heikin voitto voi siis tulla vain seuraavilla heittosarjoilla: LRR, LRLRR, LRLRLRR, LRLRLRLRR jne. (kuva 3)

Kuva 3: Heikin voittolinjat.

Lasketaan nyt tarkalleen Heikin voittotodennäköisyys, josta Tuomaksen voittotodennäköisyys saadaan komplementtisääntöä käyttäen. Koska kolikko oli painottamaton, sekä kruunan että klaavan todennäköisyys on \frac{1}{2}. Koska peräkkäiset heittokerrat ovat toisistaan riippumattomat, voidaan Heikin voittosarjat laskea kertolaskusääntöä soveltaen. Koska tarkastelu voitiin siis aloittaa ensimmäisestä klaavasta, on heittosarjan LRR todennäköisyys sama kuin kahden peräkkäisen kruunan, eli \frac{1}{2}\cdot\frac{1}{2}=\frac{1}{4}. Vastaavasti heittosarja LRLRR saadaan todennäköisyydellä \left(\frac{1}{2}\right)^4 ja niin edelleen. Koska kaikki nämä heittosarjat ovat toisistaan riippumattomia, voidaan niiden yhteinen todennäköisyys laskea summana

    \[\left(\frac{1}{2}\right)^2+\left(\frac{1}{2}\right)^4+\left(\frac{1}{2}\right)^6+\left(\frac{1}{2}\right)^8+\cdots .\]

Tämä puolestaan on geometrinen sarja, jonka suhdeluku on \left(\frac{1}{2}\right)^2=\frac{1}{4}. Näin ollen Heikin voiton todennäköisyydeksi saadaan

    \[\frac{\frac{1}{4}}{1-\frac{1}{4}}=\frac{1}{3}.\]

Komplementtisäännön nojalla Tuomas voittaa nyt todennäköisyydellä 1-\frac{1}{3}=\frac{2}{3}.

Tämä pulma löytyi Colin Beveridgen loistavalta Flying colors maths -sivustolta, jolla hän esittelee pulmaan ratkaisun parista muusta näkökulmasta. Colin on myös mainion huumorintajuinen heppu, jonka tekstejä on aina ilo lukea. Säännöllisehkön Twitter-yhteydenpitomme pohjalta Colin on lisännyt joihinkiin teksteihinsä Big in Finland -tunnisteen. Aika velikultia.