Viikon vaikea

0

Puuttuva numero

|

Colin Beveridge (suuri suomalaisten ystävä, muuten!1) esitti blogissaan hauskan lukuongelman. Seitsemännumeroinen luku on kuuden peräkkäisen parillisen luvun tulo. Tiedetään, että sen kuusi viimeistä numeroa ovat 870720. Mikä on luvun ensimmäinen numero?

Ratkaisu: Kuten Colin Beveridgekin toteaa, olisi ratkaisu raa’alla voimalla, esim. ohjelmoimalla, tylsää. Tehdään jotain hauskempaa.

Kuuden peräkkäisen parillisen luvun tulo voidaan ilmoittaa muodossa

    \[2n\cdot 2(n+1)\cdot 2(n+2)\cdot 2(n+3)\cdot 2(n+4)\cdot 2(n+5).\]

Tekijöinä ovat siis 2^6 ja kuusi peräkkäistä kokonaislukua, n, n+1, n+2, n+3, n+4 ja n+5. Kuudesta peräkkäisestä luvusta täsmälleen kaksi on kolmella jaollisia, joten koko tulon on oltava yhdeksällä jaollinen. Edelleen luku on yhdeksällä jaollinen vain, jos sen numeroiden summa on yhdeksällä jaollinen. Ja koska 8+7+0+7+2+0=24, on puuttuvan numeron oltava 3. Kysytty luku voi siis olla vain 3870720.

Varmistetaan vielä, että tämä luku todella on kuuden peräkkäisen parillisen luvun tulo. Koska 2^6 on tekijä, saadaan tällä jakamalla 60480, jonka pitäisi nyt siis olla kuuden peräkkäisen luvun tulo. Jaetaan alkutekijöihin:

    \[60480=2^6\cdot 3^3\cdot 5\cdot 7\]

.

Nyt on melko suoraviivaista alkaa päätellä tulon tekijöitä tästä. Koska 60480<10^6, eivät ainakaan kaikki tulon tekijät voi olla suurempia kuin 10. Alkutekijähajotelmasta puuttuu luku 11, joten tulon kaikkien tekijöiden on nyt itse asiassa välttämättä oltava tätä pienempiä.

Kuudesta peräkkäisestä luvusta aina täsmälleen kaksi on jaollisia kolmella, ja korkeintaan yksi yhdeksällä. Jotta 3^3 tulisi käytetyksi alkutekijähajotelmasta, on 9 välttämättä yksi tekijöistä. Toisen kolmella jaollisen tekijän on tällöin oltava 6. Koska kyse oli peräkkäisistä luvuista, myös 7 ja 8 ovat tekijöitä. Tämä jättää alkutekijöihin enää 2^2\cdot 5, eli peräkkäisten lukujen tulo on 4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9=60480. Siis edelleen

    \[$8\cdot 10\cdot 12\cdot 14\cdot 16\cdot 18=3870720.\]

4

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.