lukujonot

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

Ykkösiä, ei neliöitä

|

Osoita, ettei yksikään jonon 11, 111, 1111, 11111,\ldots jäsen ole kokonaisluvun neliö.

Ratkaisu: Jonon 11, 111, 1111, 11111,\ldots jokainen luku voidaan kirjoittaa muodossa 100m+11=4(25m+2)+3, jossa m on kokonaisluku. Näin ollen aina, kun jotain jonon luvuista jaetaan 4:llä, jakojäännökseksi jää 3.

Parilliset kokonaisluvut voidaan esittää muodossa 2n, jossa n on kokonaisluku. Näin ollen parillisten kokonaislukujen neliöt voidaan esittää muodossa (2n)^2=4n^2, eli parillisten lukujen neliöitä 4:llä jaettaessa jako menee aina tasan. Vastaavasti parittomat luvut voidaan esittää muodossa (2n+1), jolloin niiden neliöt voidaan esittää muodossa 4n^2+4n+1. Parittomien lukujen neliöitä 4:llä jaettaessa jakojäännös on siis aina 1. Siis mikään jonon  11, 111, 1111, 11111,\ldots luvuista ei voi olla kokonaisluvun neliö.

Tämä pulma on Stanfordin yliopiston matematiikkakilpailusta vuodelta 1949.

4

Jännä jono

|

Aikakauslehtien pulmapalstoilta löytyy silloin tällöin tehtäviä, joissa täytyy jatkaa loogisesti annettua lukujonoa. Periaatteessa näissä tehtävissä ei ole päätä eikä häntää, sillä ellei äärettömäksi tarkoitetun jonon muodostamissääntöä ole annettu, voidaan sitä jatkaa millä tavalla tahansa. Siis valideja jatkotapoja jonolle 2, 4, 8,\ldots olisivat 16, 32, 64,\ldots yhtä hyvin kuin 90, 0, 22, \ldots. Kysymyksen muotoilun pitäisikin siis olla, että millä säännöllä kyseinen jono voidaan muodostaa ja miten se sillä säännöllä jatkuisi.

Mutta eipä takerruta liikaa tähän semantiikkaan. Yksi suosikkijonoistani alkaa

    \[13, 1113, 3113, 132113,\ldots\]

Viikon vaikea kysymys on, kuinka sitä jatketaan loogisesti.

Ratkaisu: Jono jatkuu 1113122113, 311311222113, \ldots eli aivan kuten kommentoijamme Mikko tuossa alla jo toteaakin. Kyseessä on niin kutsuttu ”sano mitä näet”-jono, eli logiikka taustalla on sanoa, mitä jonon edellisessä termisasä on. Näin ollen termiä 13 seuraa yksi ykkönen ja yksi kolmonen, siis 1113. Tämän jälkeen tulee kolme ykköstä ja yksi kolmonen, eli 3113. Sitten yksi kolmonen, kaksi ykköstä, yksi kolmonen, eli 132113. Ja niin edelleen.

Lukujonoista kiinnostuneiden aarreaitta on Neil Sloanen jo 1960-luvulta asti ylläpitämä tietokanta The On-Line Encyclopedia of Integer Sequences eli OEIS, joka löytyy osoitteesta oeis.org. Sieltä löytyy ”ihan kaikki”, ja sivusto päivittyy yhä aktiivisesti. Tämän pulman lukujono löytyy sieltä koodilla A006715.

0

Pennirinki

|

Seuraava pulma on Charles Lutwidge Dodgsonin alias Lewis Carrollin kirjasta Pillow-Problems vuodelta 1895. Kirjassa on 72 ongelmaa, jotka Dodgson kertoo kehitelleensä ja ratkoneensa päässänsä unettomina öinä. Kirjan ongelmien vaikeustaso vaihtelee hurjasta helpohkoihin, ehkäpä yläpäätä painottaen. Tämä ongelma on sieltä kevyemmästä päästä.

Viisi roistoa istuu ringissä ja jokaisella miehellä on yhtä monta penniä. Älykkäin heistä ehdottaa pientä pennipeliä. Ensinnäkin kaikki saavat numeron, älykkäin ykkösen, seuraava kakkosen, sitten kolmonen, nelonen ja vielä vitonen. Nyt älykkäin laittaa kaikki penninsä pussiin, antaa sen kolmoselle, jonka pitää ensin ottaa kummallekin naapurilleen pussista naapurin numeron osoittama määrä pennejä. Sitten kolmosen pitää laittaa pussiin puolet siitä määrästä pennejä, joka pussissa oli sen saapuessa hänelle. Sitten kolmonen antaa pussin vitoselle, joka antaa myös pussista pennit vierustovereille, lisää puolet siitä summasta, joka pussissa oli sen tullessa hänelle, ja antaa pussin kaksi paikkaa eteenpäin. Jos sattuisi käymään niin, että rahanlisäysvaiheessa itsellä ei olisi tarpeeksi rahaa pussin täydentämiseen, saisi kenen tahansa muun paitsi numero ykkösen pennipinosta täydentää puuttuvan määrän.

Kun pussi tulee takaisin ykköselle, hän nakkaa kaksi saamaansa rahaa pussiin, vetää pussin nyörit kiinni ja pakenee vauhdilla paikalta. Muut neljä roistoa jäävät hölmistyineinä katsomaan tyhjin käsin – ryökäle nappasi kaikki rahat! Kuinka monta penniä kullakin roistolla oli aluksi?

Ratkaisu: Olkoon kullakin konnalla aluksi k kolikkoa. Peli etenee seuraavasti:

  1. Numero 3 sai pussin jossa on k kolikkoa ja hän antoi pois 2+4=6 kolikkoa. Sitten hän laittaa pussiin \frac{k}{2} kolikkoa, joten pussiin jää k+\frac{k}{2}-6=\frac{3}{2}k-6 kolikkoa.
  2. Numero 5 jakaa pois 4+1=5 kolikkoa ja puolitoistakertaistaa pussissa olleen rahasumman. Loppusumma hänen vuoronsa jälkeen on siis \frac{3}{2}\left(\frac{3}{2}k-6\right)-5.
  3. Numero 2 jakaa pois 1+3=4 kolikkoa ja puolitoistakertaistaa pussin summan. Pussin rahamäärä on hänen jälkeensä \frac{3}{2}\left(\frac{3}{2}\left(\frac{3}{2}k-6\right)-5\right)-4.
  4. Numero 4 jakaa pois 3+5=8 kolikkoa ja puolitoistakertaistaa pussin summan. Pussin rahamäärä on hänen jälkeensä \frac{3}{2}\left(\frac{3}{2}\left(\frac{3}{2}\left(\frac{3}{2}k-6\right)-5\right)-4\right)-8.
  5. Numero 1 lisää pussiin kaksi kolikkoa, jonka jälkeen pussissa on 5k kolikkoa.

Tästä saadaan yhtälö 

    \[\frac{3}{2}\left(\frac{3}{2}\left(\frac{3}{2}\left(\frac{3}{2}k-6\right)-5\right)-4\right)-8+2=5k,\]

jonka ratkaisu on k=696.

Sivumennen sanoen: olisi ehkä jäänyt ratkaisematta ilman kynän ja paperin apua. Eli onnea vain Lewis Carrollille, jos päässään yöllä tämän pyöritteli loppuun asti.

2

Pikainen summa

|

Tehdäänpä välillä pieni päässälaskutemppu. Valitse mitkä tahansa kaksi lukua ja laske ne yhteen. Jatka Fibonaccin jonon tyylisesti niin, että seuraavan luvun saat laskemalla kaksi edellistä lukua yhteen. Jatka, kunnes sinulla on kaikkiaan kymmenen lukua. Näiden kymmenen luvun summa on 11 kertaa neljänneksi viimeinen luku.

Siis esimerkiksi

    \[3+4+7+11+18+29+47+76+123+199=11\cdot 47=517.\]

Helppoa, eikö? Osoita, että homma toimii aina.

Ratkaisu: Ystäväni Maija ratkaisi ongelman seuraavasti. Merkitään kahta ensimmäistä lukua a ja b. Nyt a + b + (a+b) + (a+2b) + (2a+3b) + (3a + 5b) + (5a+8b) + (8a+13b) + (13a+21b) + (21a+34b) = 55a + 88b = 11\cdot (5a+8b).

Ratkaisu muuten mahtui kokonaisuudessaan yhteen twiittiin.

2

Paras lottorivi

|

Lotto on Italiassa keksitty arpajaispeli. Suomessa Veikkaus aloitti lottoarvonnat vuonna 1970. Lotto vakiinnutti asemansa Suomessa nopeasti suosituimpana rahapelinä, ja edellen jokaviikkoiset miljoonapotit tuovat jännitystä suureen osaan suomalaisperheistä. Tämänkertaisessa viikon vaikeassa pulmassa puututaan kaikille tutun onnenpelin matematiikkaan.

Suomalaisessa lottoarvonnassa arvotaan numeroiden 1,2,3,\ldots , 39 joukosta sattumanvaraisessa järjestyksessä seitsemän numeroa, jotka sitten ilmoitetaan oikeana ”rivinä” pienimmästä suurimpaan. Esimerkiksi jos arvotut numerot olisivat olleet arvontajärjestyksessä 2,16, 32, 12, 1, 28 ja 17, ilmoitettaisiin voittorivinä 1, 2, 12, 16, 17, 28, 32. Mikä on todennäköisin voittorivin ensimmäinen numero? Mikä on todennäköisin toinen numero? Entä mitkä ovat todennäköisimmät kolmas, neljäs, viides, kuudes ja seitsemäs numero? Onko näin löydetty numerosarja kaikkein todennäköisin lottorivi?

Ratkaisu: Tehtävän ratkaisu perustuu tuloperiaatteeseen: jos jokin kokonaisuus voidaan toteuttaa k-vaiheisesti niin, että jokaisessa vaiheessa on n_k vaihtoehtoa, on erilaisten kokonaisuuksien lukumäärä n_1\cdot n_2\cdot \cdots \cdot n_k. Toinen tarvittava esitieto on n-alkioisen joukon k-alkioisten osajoukkojen, eli k-kombinaatioiden, lukumäärä. Tätä kombinaatioden lukumäärää merkitään \binom{n}{k} (luetaan ”n yli k:n”), ja se on

    \[\binom{n}{k}=\frac{n!}{k!(n-k)!}.\]

Merkintä n! tarkoitttaa luvun n kertomaa, eli lukua n!=n\cdot (n-1)\cdot (n-2)\cdot \cdots \cdot 2\cdot 1.

Olkoon n kokonaisluku, 1\leq n\leq 39 ja olkoon 1\leq p\leq 7 luvun n paikka rivissä. Rivin numerot ennen numeroa n voidaan valita \binom{n-1}{p-1} tavalla ja sen jälkeen tulevat \binom{39-n}{7-p} tavalla. Yhteensä rivejä, jossa numero n on paikalla p, on tuloperiaatteen mukaan \binom{n-1}{p-1}\cdot\binom{39-n}{7-p} kappaletta.

Tämän jälkeen annetaan taulukkolaskentaohjelman hoitaa työ loppuun. Tuloksena on, että todennäköisimmistä numeroista koottu rivi olisi 1, 7, 13  tai 14 (yhtä todennäköiset), 20, 26 tai 27, 33 ja 39. Kokonaista lottorivitaulukkoa pääset tarkastelemaan tästä.

Näistä numeroista muodostuvat neljä lottoriviä ovat kaikkein todennäköisimmät, mutta yhtä todennäköisiä ovat kaikki muutkin 15380933 mahdollista riviä.

0

Tiukka tennisottelu

|

Tennisottelu kestää täydet viisi erää. Toisen pelaajan erissä voittamat pelit muodostavat aritmeettisen jonon. Kumpi voitti ottelun, kun kumpikin pelaajista voitti yhtä monta peliä? Kun olet löytänyt ongelmaan yhden ratkaisun, koetapa löytää vielä toinen! (Tenniksen sääntöihin voit tarvittaessa tutustua vaikka Wikipediassa.)

Tämä ongelma on peräisin Colin Beveridgeltä, joka ylläpitää erinomaista Flying Colours Maths -sivustoa sekä on valtavan mukava Twitter-tuttavuus muutenkin. Colin on muuten lisännyt blogiinsa pienenä sisäpiirivitsinä Big in Finland -tunnisteen.

Ratkaisu ongelmaan löytyy tästä.