Monthly Archives: heinäkuu 2017

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.

0

Funikulaari

|

Ystäväpiirissäni on useita, joiden mielestä funikulaari eli kiskoköysirata on yleensä vierailemisen arvoinen kohde, mikäli matkalla sellainen vastaan sattuu. Perusideahan on, että funikulaarissa on kaksi vaunua, joista toisen matkatessa ylös toinen tulee samaan aikaan alas. Jännimmissä funikulaareissa on vain yksi raide paitsi radan puolessavälissä, jossa vaunujen ohituspaikkaan on tehty pieni pätkä kaksiraiteista rataa. Mutta asiaan.

Kössi oli reissussa ja osui erityisen pitkän funikulaarin luo. Yhdensuuntainen matka-aika radalla oli peräti 15 minuuttia. Kössi lähti jalkapatikassa ala-asemalta kipuamaan kohti yläasemaa samaan aikaan kun vaunu lähti liikkeelle1. Kössi oli selvästi hitaampi kuin funikulaari. Vastaantuleva vaunu ohitti Kössin 12,5 minuutin kuluttua liikkeellelähdön jälkeen. Viikon helpot kysymykset ovat, koska jompi kumpi vaunu ohittaa Kössin seuraavan kerran ja kumpaan suuntaan vaunu on silloin menossa. (Oletetaan tehtävän vuoksi, että vaunut lähtevät ylä- ja ala-asemilta liikkeelle välittömästi sinne päästyään. Oletetaan myös, että sekä vaunut että Kössi liikkuvat tasaisella nopeudella.)

Kuva: Mark Fischer/Flickr (CC BY-SA 2.0)

Ratkaisu: Tämä pulma on versioitu Lewis Carrollin teoksessa A Tangled Tale (1885) olleesta ongelmasta.

Koska kohtaaminen tapahtuu 12 ja puolen minuutin jälkeen, on funikulaarin nopeus viisinkertainen Kössin nopeuteen verrattuna. Lasketaan ensin, koska tämä vastaantuleva vaunu ohittaa Kössin seuraavan kerran, ja todetaan sitten, että yläasemalta tuleva vaunu ei vielä silloin ole tullut vastaan.

Olkoon funikulaariradan koko pituus a ja olkoon kohta, jossa Kössi ja alhaalta tuleva vaunu kohtaavat seuraavan kerran, etäisyydellä b ala-asemalta. Olkoon t ajanhetki, jolloin kohtaaminen tapahtuu. Merkitään nyt Kössin nopeutta v_k=\frac{b}{t} ja funikulaarin nopeutta v_f=\frac{a+b}{t}. Funikulaari kulkee siis ensin koko radan ja sitten vielä matkan b rinnettä ylöspäin. Koska funikulaarin nopeus on viisinkertainen, saadaan yhtälö

    \[\frac{a+b}{t}=5\cdot\frac{b}{t},\]

josta t pois kertomalla saadaan, että

    \[b=\frac{1}{4}a.\]

Tästä voidaan päätellä, että kohtaaminen tapahtuu, kun aikaa on tarkastelun alusta kulunut koko radan kesto eli 15 minuuttia sekä neljäsosa noususta, eli 3 minuuttia ja 45 sekuntia. Näin ollen ensimmäisestä sivuutuksesta toiseen kuluu tämä 3 minuuttia ja 45 sekuntia sekä 2 ja puoli minuuttia, joka oli jäljellä ensimmäisestä radan mitasta. Siis yhteensä aikaa kuluu 6 minuuttia ja 15 sekuntia.

Koska seuraava kohtaaminen tapahtuu ennen radan puoltaväliä, on Kössin ohittava vaunu tulossa ala-asemalta.

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}\]

0

Keskinopea auto

|

H. haluaisi ajaa kahden kilometrin matkan 60 km/h keskinopeudella. Tietyön takia ensimmäinen kilometri sujuu kuitenkin vain keskinopeudella 30 km/h. Kuinka lujaa H:n pitää ajaa loppumatka?

Kuva: William Creswell / Flickr (CC BY 2.0)

Ratkaisu: Kyllä vain, tämä oli kompa. Jos H. haluaa ajaa kaksi kilometriä keskinopeudella 60 km/h, on hänellä aikaa siihen kaksi minuuttia. Kuitenkin nopeudella 30 km/h kilometrin kulkeminen kestää juuri mainitun kaksi minuuttia, joten aika on jo käytetty, kun vauhtia voitaisiin kiihdyttää. H. ei siis pysty ajamaan kahta kilometriä kahdessa minuutissa mitenkään.