2

Hoikka kolmio

Pitkä pulmailutauko on hyvä katkaista Catriona Shearerin Twitterissä esittämällä kauniilla perusgeometrian ongelmalla. Oheisessa kuvassa on neljä neliötä. Vasemmassa alanurkassa olevan neliön pinta-ala on 5. Laske sinisen kolmion pinta-ala.

 


Ratkaisu:  Aloitetaan piirtämällä korkeusjana kolmiolle, jonka kanta on pienen neliön lävistäjä. Nyt huomataan, että koska isoimman neliön (jonka sivun pituutta ei tarvitse tietää!) lävistäjä on kolmion kannan suuntainen, voidaan kolmion huippupistettä siirtää mihin tahansa ison neliön lävistäjällä, eikä kolmion ala muutu. Korkeusjana säilyy ennallaan. Kun huippu saavuttaa ison neliön alakulman, voidaan kolmion ala laskea jo helposti kahden lävistäjän avulla, mutta ollaanpa hieman ahneempia!

Kun huippu on siirretty ison kolmion alakulmaan, voidaan kolmion vasemmanpuolimmainen kärkipiste siirtää vastaavalla tavalla pitkin pienen neliön lävistäjää kohti keskikokoisen neliön kulmaa. Koska myös tässä tarvittavat lävistäjät ovat yhdensuuntaiset, voidaan kolmio muokata alan muuttumatta suorakulmaiseksi kolmioksi, jonka pinta-ala on selvästi puolet keskimmäisestä neliöstä, eli kaksi kertaa pienen neliön ala. Kysytty ala on siis 10.

0

Mustat ässät

Päivölän opiston järjestämässä Pythagoraan polku -matematiikkakilpailussa oli tänä keväänä oivallinen tehtävä. Näin se kuuluu:

Ville ja Aapo pelaavat korttipeliä. Ville nostaa tavallisesta sekoitetusta 52 kortin pakasta kortteja yhden kerrallaan, kunnes saa mustan ässän. Tämän jälkeen Aapo jatkaa korttien nostamista niin kauan kunnes hänkin saa mustan mustan ässän. Voittaja on se, kumpi saa enemmän kortteja. Jos molemmat saavat yhtä monta korttia, peli päättyy tasan. Onko peli reilu? Mikäli ei, kummalla pelaajista on etu?

Kuva: Shrayas Rajagopal / Flickr (CC BY-NC-ND 2.0)

 


Ratkaisu: Ongelman voi ratkaista monin tavoin, mutta kaunein tuntemani ratkaisu ongelmaan kuuluu näin: ajatellaan, että mustat ässät jakavat pakan kolmeen osaan. Ensimmäisessä osassa ovat kortit, jotka ovat ennen ensimmäistä mustaa ässää, toinen osa on niiden välissä ja kolmas jälkimmäisen mustan ässän jälkeen. Nyt jäljelle jäävillä 50 kortilla on jokaisella yhtä suuri todennäköisyys päätyä mihin tahansa kolmesta osasta. Peli on siis reilu.

0

Neljäksi jaettu neliö

Paul Sloanen ja Des MacHalen kirjassa Mathematical Lateral Thinking Puzzles on yksinkertaisen näköinen ongelma, jonka ratkaiseminen ei olekaan ihan niin simppeliä.

Jaa neliö neljäksi suorakulmioksi siten, että nämä suorakulmiot voidaan järjestellä uudelleen kahdeksi erikokoiseksi neliöksi.


Ratkaisu: Oheisessa kuvassa on neliö, jonka sivun pituus on 5. Tällä tavalla leikaten se voidaan järjestellä neliöiksi, joiden sivujen pituudet ovat 3 ja 4. Sloanen ja MacHalen mukaan muita toimivia sivunpituussuhdekombinaatioita ei ole olemassa. Yllättävää!

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)


Ratkaisu: Pulma on varsin originaali, en ole törmännyt aiemmin tällaiseen, eikä ole Petrikään, joka pulman on laatinut. Hän on myös tarkastanut, ettei pulmaan löydy kuin yksi ratkaisu. Tietenkinhän pulma voidaan ratkoa myös kokeilemalla, mahdollisia järjestyksiä on vain 8!=40320 kappaletta, mutta mekaaninen ratkaisu olisi vähän tylsä. Mennään siis loogisella päättelyllä tekemääni ratkaisuun.

Poimitaan helpot ensin. Jo tehtävänanto lupaa, että a_2=2. Tästä seuraa heti, että a_3=a_{a_2}-1=a_2-1=2-1=1.

Seuraavaksi joudutaan jo vähän pohtimaan. Koska rekursiokaavan mukaan a_n=a_{a_{n-1}}-1, kun n=2, 3, \ldots, 9, on a_n<a_{a_{n-1}}. Koska a_1 kuuluu rekursiokaavan ulkopuolelle, on tehtävä johtopäätös, että koko jonon suurin termi on a_1=9. Tämän perusteella puolestaan ratkeaa, että a_4=a_{a_3}-1=a_1-1=9-1=8. Edelleen, koska a_2=a_{a_1}-1=a_9-1, saadaan termiksi a_9=a_2+1=2+1=3.

Järjestämättä ovat vielä arvot 4, 5, 6 ja 7 termeiksi a_5, a_6, a_7 ja a_8. Koska a_5=a_{a_4}}-1=a_8-1 ja koska a_8=a_{a_7}-1, niin a_5=a_{a_7}-2. Nyt minulle tuli hetkeksi tenkkapoo, ja myönnänkin edenneeni seuraavaan vaiheeseen arvaamalla1. Käytettävissä olevien lukujen nojalla tämä jättää vaihtoehdot a_5=4 tai a_5=5. Näistä vaihtoehto a_5=4 johtaa ristiriitaan (kokeile vain!).

Kun a_5=5, on edellä olleen yhtälön nojalla a_8=6. Nyt myös a_6=a_{a_5}-1=a_5-1=5-1=4 ja vielä a_7=a_{a_6}-1=a_4-1=8-1=7.

Koko jono on siis

    \[a_1=9, a_2=2, a_3=1, a_4=8, a_5=5, a_6=4, a_7=7, a_8=6, a_9=3.\]

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

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

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

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.

0

Kissa kiinnostaa

Hieman olen miettinyt, kuinka paljon vielä kehtaan tänne Alex Bellosin loistavaa The Guardianin pulmapalstaa suomentaa, mutta menköön nyt vielä ainakin tämän kerran. Voi kai tätä jonkinlaisena toimituksellisena työnä sentään pitää. Tämänkertainen pulma on mukaelma muutaman vuoden takaa The New York Timesissa julkaistusta ”prinsessapulmasta”. Ja tässä se tulee.

Käytävällä on ovia rivissä, ja yhden oven takaa löytyy kissa. Kissa! Sinun tehtäväsi on löytää kyseinen luomakunnan kruunu. Mutta säännöt ovat vaativat: saat arvata vain kerran, jonka jälkeen kissa siirtyy (näennäisen!) sattumanvaraisesti yhden oven joko oikealle tai vasemmalle.

Viikon helppo pulma on löytää kissa korkeintaan neljännellä arvauksella, kun ovia on rivissä neljä.

Viikon vaikea pulma on selvästi haastavampi: mikä on pienin määrä arvauksia, joilla löydät kissan varmasti, kun kissa piileskelee seitsemän oven takana?

Selvennyksiksi vielä todettakoon, että kissa siirtyy jokaisen arvauksen jälkeen, ja että ovet ovat tosiaankin rivissä, eli vasemmanpuolimmainen ja oikeanpuolimmainen ovi ovat käytävän reunoilla, eikä niistä ole yhteyttä toisiinsa ”nurkan ympäri”.

Kuva: Abby Rosenberg / Flickr (CC BY-NC 2.0)


Ratkaisu: Tämä pulma on erinomainen esimerkki eräästä matemaattisesta ongelmanratkaisumenetelmästä, jossa monimutkaista pulmaa lähestytään ennen yksinkertaisemman erikoistapauksen kautta ja sitten pyritään löytämään menetelmä, joka sopii myös monimutkaisemmille tapauksille. Ajatellaanpa vaikka tätä pulmaa yksinkertaisimmillaan. Jos ovia olisikin vain yksi, olisi kissa varmasti sen takana. Jos taas ovia olisi kaksi, niin ellei kissa heti olisi arvatun oven takana, siirtyisi se sinne seuraavaksi kerraksi. Oikeastaan kolmen oven versio on ensimmäinen mielekäs vaihe, jossa yksi pulman lopulliselle ratkaisemiselle keskeinen idea tulee ensimmäistä kertaa esiin: jos kissa ei ole keskioven takana, on sen oltava reunassa, josta se siirtyy keskioven taakse seuraavalle kierrokselle. Kissa ei siis voi olla kahta kertaa peräkkäin reunaoven takana.

Tehdään nyt ratkaisuista kaaviokuvat. Merkitään avattua ovea A:lla ja mahdollista kissan paikkaa K:lla. Esittelen tässä nyt pisimmät tiet – kissahan voisi hyvällä onnella tulla vastaan jo aiemminkin. Mutta seuraavat reitit johtavat varmasti ratkaisuun. Neljän oven ratkaisualgoritmi on seuraava:

    \[\begin{array}{|c|c|c|c|}K&A&K&K\\ \hline&K&A&K\\ \hline K&&A&\\ \hline &A&&\end{array}\]

Pienellä pohdinnalla ratkaisumalli alkaa hahmottua. Muutamia huomioita voi tehdä nopeasti. Ei kannata aloittaa reunalta, se ei johda mihinkään. Jos kissa on reunalla, ei se voi seuraavalla kerralla siellä olla. Jos tästä laajennetaan viiden oven tapaukseen, huomataan myös se, että keskimmäisestä ovesta aloittaminen ei myöskään toimi. Miten voidaan alkaa rajoittaa kissan paikkoja? Voidaanko osa ovista rajata pysyvästi kissavapaaksi alueeksi?

Itse painin aika tovin viiden oven ongelman kanssa, mutta sitten juttu alkoi aueta. Sen innoittamana kuuden oven versio ratkesi nopeasti, eikä seitsemän ovea ollut sitten enää sen kummempi haaste. Alex Bellosin linkkaaman alkuperäisen pulman ovien lukumäärä oli 17, mutta sama ratkaisualgoritmi toimii siihenkin. Jos ovia on k kappaletta, arvauksia tarvitaan aina korkeintaan 2k-4. Tässä ratkaisu seitsemälle ovelle. Arvauksia tarvitaan korkeintaan kymmenen. En selitä enempää. Tutki itse (ja tule vasta sitten tarkistamaan ratkaisu)!

    \[\begin{array}{|c|c|c|c|c|c|c|}K&A&K&K&K&K&K\\ \hline &K&A&K&K&K&K\\ \hline K&&K&A&K&K&K\\ \hline &K&&K&A&K&K\\ \hline K&&K&&K&A&K\\ \hline&K&&K&&A&\\ \hline K&&K&&A&&\\ \hline &K&&A&&&\\ \hline K&&A&&&&\\ \hline &A&&&&&\end{array}\]