cb P 1T

(1)

pitkän

matematiikan lisäsivut

Ville Tilvis

täsmällinen päättely

A

B C

D

1

(2)

P ITKÄN MATEMATIIKAN LISÄSIVUT 1 T ÄSMÄLLINEN PÄÄTTELY

Ville Tilvis ja Esa V. Vesalainen

Pitkän matematiikan lisäsivut 1: Täsmällinen päättely Viipurin Reaalikoulu Oy

Maunulan yhteiskoulu ja Helsingin matematiikkalukio

Matematiikan opetuksen valtakunnallinen kehittämistehtävä Harppi

Helsinki 2020 1. Painos

Jotta kirjan käyttö olisi mahdollisimman mutkatonta, sen sisältö on lisensoitu avoimella Creative Commons Nimeä 4.0 Kansainvälinen -käyttöluvalla.

cb

https://creativecommons.org/licenses/by/4.0/deed.fi

Kannen suunnittelu Salli Kulmala ISBN 978-952-69550-0-1 (nid.) ISBN 978-952-69550-1-8 (PDF) Next Print Oy, Helsinki

(3)

Sisältö

Esipuhe 5

1 Täsmällinen päättely 6

Tärvelty shakkilauta . . . 6

Välin ]0,1[ suurin luku . . . 7

Virheellinen todistus: 1=2 . . . 8

p2 on irrationaaliluku . . . 9

2 Laatoituksia ja värityksiä 10 Harjoitustehtäviä . . . 12

3 Ramseyn teoriaa 15 Harjoitustehtäviä . . . 17

4 Luvut ja äärettömyys 18 Äärettömyyksien vertailu . . . 19

Numeroituvuus . . . 21

Rationaalilukujen mahtavuus . . . 21

Ylinumeroituvuus . . . 23

Mikä luku voisi olla 0,9999...? . . . 24

Harjoitustehtäviä . . . 26

5 Vaikeiden ongelmien ratkaiseminen 27 Ongelmanratkaisijan työkalupakki . . . 28

Taikasaari . . . 29

(4)

6 Lukujonot ja hyvinjärjestysperiaate 32

Lukujono . . . 32

Fibonaccin luvut ja rekursio . . . 33

Hyvinjärjestysperiaate . . . 34

Ensimmäiset vihjeet 42

Toiset vihjeet 55

Lähteet 70

(5)

Esipuhe

Pitkän matematiikan lisäsivut ovat itseopiskelumateriaalia niille, jotka kaipaavat haasteita ja haluavat laajentaa matematiikan osaamistaan lukio-oppimäärän ulko- puolelle. Lisäsivuihin on valittu aihepiirejä, joita lukiossa ei yleensä kohtaa, mutta joihin matematiikasta innostuneen voisi olla kiintoisaa ja palkitsevaa tutustua.

Materiaali sisältää lyhyet teoriaosiot ja runsaasti harjoitustehtäviä, joihin on kat- tavat vihjeet ja useimpiin toiset vihjeet. Tehtäviä on syytä yrittää aina ensin itse, mutta vihjeet ja toiset vihjeet on tarkoitettu käytettäviksi. Monet tehtävistä ovat huomattavan vaikeita, eikä kannata huolestua, jos osa niistä jää ratkaisematta.

Pitkän matematiikan lisäsivut 1 johdattaa matemaattisen ajattelun eri muotoihin.

Täsmälliseen päättelyyn perehdytään laatoitusten, Ramseyn teorian, äärettömyyk- sien sekä lukujonojen parissa. Kokoelma pulmatehtäviä harjaannuttaa luovaa ongelmanratkaisutaitoa.

Haluamme kiittää kaikkia kollegoita ja opiskelijoita, jotka ovat antaneet kannus- tavaa palautetta kirjan luonnoksista. Lisäksi Ville Tilvis haluaa kiittää perhettään tuesta kirjaprojektille.

Kaikista virheistä, puutteista ja parannusehdotuksista toivotaan sähköpostia Ville Tilvikselle (ville.tilvis (at) mayk.fi).

Antoisia hetkiä lisäsivujen parissa!

Helsingissä ja Vantaalla 20.12.2020, Ville Tilvis ja Esa V. Vesalainen

Opettaja! Tehtävien ratkaisut voi tilata osoitteesta ville.tilvis (at) mayk.fi

(6)

1 Täsmällinen päättely

Matematiikka on ajattelua täsmällisimmillään. Kun matemaattinen väite on kerran perusteltu oikeaksi – eli todistettu – se on varmaa tietoa eri tavalla kuin mikään kokeellinen tulos. Voi olla, että ymmärryksemme painovoimasta ei ole aivan oikea, mutta kahden parittoman luvun summa on varmasti parillinen.

Mistä ”todistamisen” varmuus kumpuaa? Tämä on syvällinen kysymys, jota ei mis- sään nimessä ole ratkaistu lopullisesti. Emme kuitenkaan uppoudu nyt filosofiaan, vaan lähestymme asiaa esimerkkien kautta.

”Todistaminen” tai ”osoittaminen” kuulostaa kovin juhlalliselta, mutta näillä sa- noilla tarkoitetaan vain, että jokin asia on perusteltu täsmällisesti ja aukottomasti.

Tarkastellaan muutamaa esimerkkiä.

Tärvelty shakkilauta

Shakkilaudasta on poistettu vastakkaiset kulmat kuvan mukaisesti.

Voiko tällaisen tärvellyn shakkilaudan peittää kahden vierekkäisen ruudun muotoisilla dominopaloilla? Palat eivät saa mennä päällekkäin tai reunojen yli.

(7)

LUKU 1. TÄSMÄLLINEN PÄÄTTELY

Muutaman kokeilun jälkeen alkaa tuntua siltä, että tämä on mahdotonta. Miten sen voisi todistaa? Erilaisia vaihtoehtoja palojen asettelulle on valtavasti, joten niiden läpi käyminen käsin ei ole realistinen vaihtoehto. Jos urakka halutaan siis osoittaa mahdottomaksi, täytyy joko

1. Kirjoittaa tietokoneohjelma, joka käy kaikki vaihtoehdot läpi ja tarkistaa, ettei mikään toimi.

2. Keksiä jotakin yksinkertaisempaa.

Suosimme toki jälkimmäistä vaihtoehtoa. Matematiikan helmiä ovat tilanteet, joissa yksinkertainen argumentti ratkaisee sotkuisen näköisen tilanteen. Tässä on ratkaisu:

Todistus.Tärveltyä shakkilautaa ei voi peittää dominopaloilla, sillä jokainen pala peittää yhden mustan ja yhden valkoisen ruudun. Laudassa on kaksi mustaa ruutua enemmän kuin valkoisia, joten vähintään kaksi mustaa ruutua jää peittä- mättä.

Kuinka vaivatonta ja eleganttia!

Huomautus.Todistuksen loppuun on usein tapana kirjoittaa pieni selventävä neliö osoittaamaan, että todistus on valmis. Tämä tapa on kopioitu sanomaleh- tiartikkeleiden lopetusmerkeistä. Toinen vaihtoehto on kirjoittaa m.o.t. (”..., mikä oli todistettava”) tai sama latinaksi: Q.E.D. (”quod erat demonstrandum”). Tässä tekstissä emme juuri käytä mitään näistä, koska lähes joka tehtävän ja esimerkin ratkaisu on jonkinlainen todistus joka tapauksessa.

Välin ]0,1[ suurin luku

Mikä on välin ]0,1[ suurin luku? Merkinnällä ]0,1[ tarkoitetaan joukkoa, joka koostuu kaikista reaaliluvuistax, joille pätee 0<x<1. Toisin sanoen, mikä on suurin lukua 1 pienempi luku?

Vastaukseksi tarjotaan usein lukua 0,999..., mutta tämän desimaaliesityksen ainoa luonnollinen tulkinta itse asiassa on, että kysessä on luku 1, kuten sivulla 24 perustellaan. Hieman yllättäen välin ]0,1[ suurinta lukua ei ole olemassa! Perustellaan tämä.

Väite.Välillä ]0,1[ ei ole suurinta lukua.

Todistus.Oletetaan, että välin ]0,1[ suurin luku ona. Koskaakuuluu kyseiselle välille, täytyy ollaa<1. Merkitäänb=1−a. Tilanne on siis tämä:

(8)

LUKU 1. TÄSMÄLLINEN PÄÄTTELY 1

0 a

b

Tarkastellaan lukuaa+^b₂. Se on lukujenaja 1 keskiarvo, ja se on suurempi kuin a, mutta pienempi kuin 1. Lukua+^b₂ kuuluu siis välille ]0,1[, mutta on suurempi kuina.

1

0 a

b a+^b₂

Siis: Jos mikä tahansa lukuaon välin ]0,1[ suurin luku, niin se ei olekaan tämän välin suurin luku, koskaa+^b₂ on suurempi. Tämä on ristiriita, joten mikään luku ei voi olla välin ]0,1[ suurin.

Edellä käytetty tapa todistaa jokin seikka mahdottomaksi ristiriidan kautta on hyvin näppärä työkalu, mutta voi vaatia hieman totuttelua.

Virheellinen todistus:1=2

Aloitetaan tilanteestaa=b, missäajabovat reaalilukuja. Kertomalla puolittain luvullaasaadaan

a²=ab.

Sen jälkeen lisäämällä yhtälöön puolittain lukua²−2absaadaan a²+a²−2ab=ab+a²−2ab,

eli

2a²−2ab=a²−ab.

Tämä sievenee muotoon 2·¡

a²−ab¢

=1·¡

a²−ab¢ . Jakamalla luvullaa²−absaadaan lopuksi

2=1.

Mikähän meni pieleen?

Ongelman ydin on siinä, että kuna =b, erotus a²−ab on nolla. Viimeisessä vaiheessa siis jaetaan nollalla, mikä tunnetusti ei ole hyvä idea.

Päättely on pätevä vain, jos sen jokainen vaihe on moitteeton!

(9)

LUKU 1. TÄSMÄLLINEN PÄÄTTELY p2on irrationaaliluku

Luvunp

2 irrationaalisuuden perustelu on klassinen todistus, joka on hieman edellisiä esimerkkejä monimutkaisempi.

Väite.Lukup

2 ei ole rationaaliluku.

Todistus.On kaksi vaihtoehtoa: jokop

2 on rationaaliluku, tai se on irrationaaliluku. Osoitetaan, että se ei voi olla rationaaliluku.

Josp

2 olisi rationaaliluku, se voitaisiin kirjoittaa murtolukuna muodossa p2=m

n,

missämjanovat kokonaislukuja, jan6=0. Voidaan lisäksi päättää tutkia tapausta, jossa murtolukum

n on supistettu. Sievennetään hieman:

p2=m

n ||( )²

2=m²

n² || ·n²

2n²=m²

Luku 2n²on parillinen, joten myös luvunm²täytyy olla parillinen (sillä nämä luvut ovat yhtäsuuret). Siksi myös luvunmon oltava parillinen. Voidaan siis kirjoittaa m=2k, missäkon kokonaisluku. Jatketaan:

2n²=m² ||m=2k

2n²=(2k)²

2n²=4k² || : 2

n²=2k²

Nyt myös luvunnon oltava parillinen saman päättelyn perusteella kuin aiemmin.

Sekä luvunmettä luvunntäytyy siis olla parillisia, jotenm

n ei voi olla supistettu murtoluku. Lukuap

2 ei siis voi kirjoittaa supistettuna murtolukuna, joten se ei ole rationaaliluku.

Täsmällinen päättely on vaikeaa, ja oikean lähestymistavan löytäminen vaatii sekä kokemusta että luovuutta. Loppuosa tästä kirjasta esittelee erilaisia tapoja päätellä ja perustella täsmällisesti. Osa harjoitustehtävistä osoittautuu todennäköisesti vaikeiksi, joten hyödynnä vihjeitä!

(10)

2 Laatoituksia ja värityksiä

Matematiikassa laatoituksella tarkoitetaan tilanteita, joissa kuvio peitetään pie- nemmillä kuvioilla eli ”laatoilla”. Laatat eivät mene päällekkäin, ne eivät saa olla edes osittain laatoitettavan alueen ulkopuolella, eikä laattoja saa pilkkoa osiin.

Arkielämän esimerkki laatoituksesta olisi vaikkapa kylpyhuoneen lattian laatoit- taminen kaakeleilla. Tosin erona puhtaaseen matematiikkaan kylpyhuoneessa laattoja pilkotaan surutta tilaan sopiviksi.

Osa laatoitettua lattiaa

Tässä luvussa keskitymme todistamaan eri tavoin, että tietynlaiset laatoitukset ovat mahdottomia. Edellisessä kappaleessa esitetty tärvellyn shakkilaudan ongelma on tästä klassinen esimerkki. Tarkastellaan kahta muutakin esimerkkiä.

Esimerkki. Voiko 4×5-suorakaiteen laatoittaa seuraavilla viidellä laatalla?

Ratkaisu. Jaetaan suorakaide 1×1-ruuduiksi, ja väritetään ne kuten shakkilauta.

0Z0Z0

Z0Z0Z

0Z0Z0

Z0Z0Z

(11)

LUKU 2. LAATOITUKSIA JA VÄRITYKSIÄ

Näin saadaan 10 mustaa ja 10 valkeaa ruutua. Jokainen laatoista peittää kaksi valkeaa ja kaksi mustaa ruutua, paitsi T-laatta, joka peittää aina joko kolme valkeaa ja yhden mustan ruudun, tai kolme mustaa ja yhden valkean ruudun. Siten anne- tut viisi laattaa peittävät aina eri määrät mustia ja valkeita ruutuja, ja erityisesti 4×5-suorakaidetta ei voi laatoittaa niillä.

Tilanne ei muutu, vaikka laattoja miten kiertäisi tai kääntäisi toisin päin peili- kuvakseen. (Ja muut kuin 90 asteen kierrot eivät selvästikään voi toimia, koska laattojen täytyy sopia yhteen sekä toistensa että suorakulmion reunojen kanssa.)

Esimerkki 2. Usein laatoituksen mahdottomuus on kätevää perustellaan jollakin muulla värityksellä kuin shakkilautakuviolla. Todistetaan esimerkiksi, että 8×8-ruudukkoa ei voi peittää 12 kappaleella 5×1-paloja ja yhdellä 4×1-palalla.

×12

×1

Ratkaisu. Shakkilautaväritys ei nyt vaikuta hyödylliseltä, sillä jokainen 5×1-pala peittäisi joko kaksi tai kolme mustaa ruutua, mikä ei suoraan johda ristiriitaan.

Ruudukko voidaan kuitenkin värittää esimerkiksi näin:

Mustia ruutuja on nyt 14 kappaletta, ja kukin 5×1- ja 4×1-paloista voi peittää niistä vain yhden. Koska paloja on käytettävissä vain 13 kappaletta, ainakin yksi musta ruutu jää peittämättä ja laatoitus on siis mahdoton.

Laudan sopiva väritys valitaan siis sen mukaan, mitä ollaan todistamassa.

(12)

LUKU 2. LAATOITUKSIA JA VÄRITYKSIÄ Harjoitustehtäviä

Tehtävä 1. Osoita, että sekä 4×4- että 8×8-ruudukon voi laatoittaa tällaisilla 1×1-neliöistä koostuvilla T-laatoilla.

Osoita sitten, että 10×10-ruudukkoa ei voi laatoittaa tällaisilla T-laatoilla.

Vihje s. 42→ Toinen vihje s. 55→

Tehtävä 2. Osoita seuraavan värityksen avulla, että 8×8 -ruudukkoa ei voi laatoittaa 15 kappaleella neljän ruudun L-paloja ja yhdellä 2×2-neliöllä.

×15 ×1

Tehtävä 3. Osoita, että 8×8-ruudukkoa ei voi laatoittaa 15 T-laatalla ja yhdellä 2×2-laatalla.

×15 ×1

Tehtävä 4. Osoita, että 10×10-neliötä ei voi laatoittaa 1×4-laatoilla.

(13)

Tehtävä 5. Neliön mitat ovat 7×7 ruutua, ja se yritetään laatoittaa kahdella eri tavalla:

a) 12 kpl kolmen ruudun L-paloja, 3 kpl 2×2-neliöitä ja yksi 1×1-neliö.

b) 8 kpl kolmen ruudun L-paloja, 6 kpl 2×2-neliöitä ja yksi 1×1-neliö.

Toinen näistä tavoista on mahdollinen ja toinen mahdoton. Kumpi on kumpi?

Perustele kummastakin, miksi se on mahdollinen tai mahdoton.

×12

×3

×1

×8

×6

×1

Tehtävä 6. Mielenkiintoista kyllä 10×10-ruudukkoa ei voi laatoittaa millään yhdistelmällä neljän ruudun Z-paloja ja 4×1-paloja.

Alla on kolme erilaista väritystä. Minkä avulla edellä esitetty väite voitaisiin todistaa?

Väritys 1 Väritys 2 Väritys 3

(14)

Tehtävä 7. Suorakulmainen lattia on laatoitettu 2×2-laatoilla ja 1×4-laatoilla.

Valitettavasti yksi 2×2-laatta menee rikki, ja varastosta löytyy vain yksi 1×4-laatta.

Osoita, että lattiaa ei voi laatoittaa jäljelle jääneillä ehjillä laatoilla ja varastosta löytyneellä laatalla, vaikka laatat asettelisi uuteen järjestykseen.

Tehtävä 8. Tarkastellaan tällaista tasasivuisista kolmioista muodostuvaa ruudukkoa:

Voiko tämän ruudukon laatoittaa seuraavan muotoisilla laatoilla?

(15)

3 Ramseyn teoriaa

Seuraava ongelma on eräs klassisimmista esimerkeistä siitä, miten matematiikassa saavutetaan monimutkaisia tuloksia yksinkertaisilla työkaluilla. Tällaisia ilmiöitä tarkastellaan englantilaisen Frank P. Ramseyn (1903–1930) mukaan nimetyssä Ramseyn teoriassa.

Esimerkki. Tarkastellaan kuutta ihmistä, joista ketkä tahansa kaksi joko tuntevat toisensa tai eivät tunne toisiaan. Osoita, että heidän joukostaan löytyy aina kolme, jotka kaikki tuntevat toisensa, tai kolme, joista ketkään kaksi eivät tunne toisiaan.

Huomautus.Kuusi henkilöä voivat tuntea toisiaan tai olla tuntematta toisiaan 2¹⁵=32768 eri tavalla.

Ratkaisu. Tarkastellaan yhtä näistä kuudesta henkilöstä, vaikkapa henkilöäA.

Täytyy joko löytyä ainakin kolme muuta henkilöäB,CjaDjotka kaikki tuntevat henkilönA, tai ainakin kolme henkilöäB,CjaD, jotka kaikki ovat tuntemattomia henkilölleA. Muutoin nimittäin muita henkilöitä olisi korkeintaan 2+2=4.

Merkitään sitä, että kaksi ihmistä tuntevat toisensa tavallisella viivalla ja sitä, että he eivät tunne toisiaan, katkoviivalla . Tarkastellaan ensin tapausta, jossaAtuntee ainakin kolme henkilöäB,CjaD.

A B

C

D

1

Jos nyt jotkut kaksi henkilöäXjaY henkilöistäB,CjaDtuntevat toisensa, niinA, XjaY ovat kolme henkilöä, jotka kaikki tuntevat toisensa.

A B

C

D

A B

C

D

A B

C

D

(16)

LUKU 3. RAMSEYN TEORIAA

Jos taas ketkään kaksi henkilöistäB,CjaDeivät tunne toisiaan, niin silloin he ovat kolme henkilöä, joista ketkään kaksi eivät tunne toisiaan.

A B

C

D

Tarkastellaan sitten jälkimmäistä tapausta, jossa1 Aei tunne ketään henkilöistäB, CjaD. Tämä tapaus on täysin samanlainen kuin edellinenkin.

A B

C

D

Jos nyt jotkut kaksi henkilöäX jaY henkilöistä1 B,C jaD ovat toisilleen tuntemattomia, niinA,X jaY ovat kolme henkilöä, joista ketkään kaksi eivät tunne toisiaan.

A B

C

D

1

A B

C

D

1

A B

C

D

Jos taas henkilötB,C jaD kaikki tuntevat toisensa, niin silloin he ovat kolme1 henkilöä, jotka kaikki tuntevat toisensa.

A B

C

D

Väite siis pätee kaikissa tapauksissa, ja olemme valmiit.1

(17)

LUKU 3. RAMSEYN TEORIAA Harjoitustehtäviä

Tehtävä 9. Kolme ihmistä tapaa. Osoita, että joku heistä tuntee molemmat muut, tai että joku heistä ei tunne kumpaakaan muuta.

Tehtävä 10. Neljän kaupungin välillä kulkee kuusi rautatietä, jotka yhdistävät jokaisen kaupungin jokaiseen toiseen.

Kaupunkien välillä operoi kaksi junayhtiötä, Blue Lines ja Red Lines. Reitit kilpai- lutetaan niin, että kutakin kuudesta reitistä liikennöi vain toinen yhtiöistä.

Osoita, että kilpailutuksen lopputuloksesta huolimatta mistä tahansa kaupungista pääsee kaikkiin muihin käyttäen vain yhden yhtiön junia. (Suoraa yhteyttä ei välttämättä ole, mutta kiertämällä toisten kaupunkien kautta pääsee minne vain.) Huomautus: Tehtävän yleistys n kaupungille on harjoitustehtävänä 29 sivulla 36.

Tehtävä 11. Tarkastellaan kymmentä ihmistä, joista ketkä tahansa kaksi joko tuntevat toisensa tai eivät tunne toisiaan. Osoita, että näiden kymmenen ihmisen joukosta löytyy neljä ihmistä, jotka kaikki tuntevat toisensa, tai kolme ihmistä, joista ketkään kaksi eivät tunne toisiaan.

Huomautus.Sama todistus toimii luonnollisesti väitteeseen, jossa tunteminen ja tuntemattomuus vaihdetaan keskenään.

Huomautus 2.Osoittautuu, että monimutkaisemmalla argumentilla voi osoittaa, että luvun kymmenen voi korvata tässä luvulla yhdeksän ja väite pitää edelleen paikkansa. Tätä emme tässä todista.

Tehtävä 12. Osoita, että kahdestakymmenestä ihmisestä jotkin neljä kaikki tuntevat toisensa tai jotkin neljä ovat toisilleen tuntemattomia.

Tehtävä 13. Seitsemäntoista tutkijaa käy keskenään kirjeenvaihtoa kolmesta aiheesta niin, että jokaiset kaksi heistä käyvät keskenään kirjeenvaihtoa täsmälleen yhdestä aiheesta. Osoita, että jotkin kolme tutkijaa käyvät keskenään kirjeenvaihtoa samasta aiheesta.

(18)

4 Luvut ja äärettömyys

Laskemisen perusta on lukumäärää osoittavissa luvuissa 1, 2, 3, 4, ja niin edelleen.

Ihmiskunnan laskentatarpeiden kasvaessa käyttöön on vuosituhansien kuluessa otettu yhä monimutkaisempia lukuja. Luvut eivät ole mitenkään itsestään selviä (negatiivisia lukuja hyljeksittiin vielä 1500-luvulla), mutta modernin koulumate- matiikan kasvatti on tottunut operoimaan näiden lukujoukkojen kanssa.

Joukko Sisältää luvut

luonnolliset luvutN 0, 1, 2, 3, ...

kokonaisluvutZ ...,−2,−1, 0, 1, 2, 3, ...

rationaaliluvutQ luvut muotoam

n, missämjankokonaislukuja jan6=0.

reaaliluvutR rationaalilukujen lisäksi muutkin lukusuoran luvut Joissakin matemaattisissa teksteissä luku 0 lasketaan luonnolliseksi luvuksi, joissakin ei. Tässä tekstissä noudatetaan käytäntöä, jossa 0 on luonnollinen luku.

Jokainen edellä mainituista lukujoukoista on edellisen laajennos: kokonaisluvut sisältävät luonnolliset luvut ja negatiiviset luvut; rationaaliluvut sisältävät kokonaisluvut ja murtoluvut; reaaliluvut sisältävät rationaaliluvut ja irrationaaliluvut.

N Z Q R C

0 8

−2 −105

2 3

−1

7 2,5

p2 0,101001000100001...

i 3−4i

(19)

LUKU 4. LUVUT JA ÄÄRETTÖMYYS

Reaalilukujen joukkoa voidaan vielä täydentääkompleksilukujenjoukollaC. Komp- leksilukuihin palataan Pitkän matematiikan lisäsivujen osassa 2.

Äärettömyyksien vertailu

Kuinka paljon erilaisia lukuja sitten on? Luonnollisia lukuja on äärettömän monta, mikä tarkoittaa esimerkiksi sitä, että luonnollisten lukujen lukumäärä on suurempi kuin mikään positiivinen luku. Tällä tavalla ajateltuna ääretön itse ei kuulu mihinkään tässä käsiteltyyn lukujoukkoon: se ei ole luonnollinen luku eikä edes reaaliluku.

Symbolia∞käytetään monessa eri merkityksessä, muun muassa tarkoittamaan mitä tahansa ääretöntä lukumäärää, toisin sanoen äärellisen vastakohtana. Seu- raavassa haluamme vertaillaerilaisiaäärettömiä, joten∞-symboli on liian epä- täsmällinen tähän käyttöön. Saksalainen matemaatikko Georg Cantor nimittäin todisti vuonna 1874, että äärettömiä joukkoja todella on eri kokoisia.

Joukon alkioidenmahtavuutta(mikä äärellisillä joukoilla tarkoittaa samaa kuin alkioiden lukumäärä) merkitään operaattorilla #, eli esimerkiksi suomalaisten aakkosten vokaalien joukolle voidaan kirjoittaa

#{a, e, i, o, u, y, å, ä, ö}=9.

Luonnollisia lukuja on äärettömän monta, joten #Nei voi olla mikään äärellinen luku. Toisaalta myös kokonaislukuja on äärettömän monta. Onko kokonaislukujen mahtavuus sama kuin luonnollisilla luvuilla vai suurempi? Päteekö

#N=#Z vai #N<#Z? Miten näitä äärettömyyksiä vertaillaan?

Vertailuperiaate

Kahden joukon mahtavuuksien vertailussa toimivaksi on osoittautunut seuraava vertailuperiaate:

Jos kahden joukon alkioista voidaan muodostaa parit siten, että kum- mastakaan joukosta ei jää yhtään alkiota paritta, ja joka luvulla on vain yksi pari, niin silloin joukoissa on yhtä monta alkiota.

Periaatteelle on ehdotettu nimeä Humen periaate, jota ei pidä sekoittaa tunne- tumpaan Humen giljotiiniin.

Tätä vertailuperiaatetta voi soveltaa muinaiseen rusettiluisteluun, jossa luisteli- joilla oli (numeroituja) punaisia ja sinisiä rusetteja, ja jokaisen tuli löytää oma pari

(20)

vastakkaista väriä. Jos tällaisessa luistelussa kaikille löytyy pari, voidaan päätellä punaisia ja sinisiä rusetteja olevan yhtä paljon.

Rusetit järjestykseen

Tällä vertailuperiaatteella luonnollisia lukuja ja kokonaislukuja on yhtä monta!

Voidaan nimittäin tehdä tällaiset parit:

N Z

0 0

1 1

2 −1

3 2

4 −2

5 3

6 −3 ... ...

Nollan pari on nolla, ja tämän jälkeen parittomilla luonnollisilla luvuilla nume- roidaan positiiviset ja parillisilla negatiiviset luvut. Jokaiselle luvulle löytyy pari, joten joukot ovat yhtä mahtavat: #N=#Z.

Tulos on yllättävä: miten muka kokonaislukuja ei olisi enemmän, sisältyväthän kaikki luonnolliset luvut kokonaislukuihin! Tähän on kuitenkin tyydyttävä, mikäli hyväksytään vertailuperiaatteksi yllä esitetty ”rusettiluisteluperiaate”.

Sivuhuomiona todettakoon, että muitakin vertailuperiaatteita on. Esimerkiksi joidenkin lukujoukkojen vertailussa voidaan käyttää käsitettätiheys, jolloin luon- nollisten lukujen tiheys on 1 ja parillisten luonnollisten lukujen tiheys¹₂. Nämä joukot ovat kuitenkin yhtä mahtavat, kuten saat harjoitustehtävässä 14 perustella.

(21)

LUKU 4. LUVUT JA ÄÄRETTÖMYYS Numeroituvuus

Jos joukon alkiot voidaan asettaa pareiksi luonnollisten lukujen (tai jonkin sen osajoukon) kanssa, joukkoa sanotaannumeroituvaksi. Tällä hetkellä elävien ihmis- ten joukko on numeroituva, mutta äärellinen; kokonaislukujen joukko on myös numeroituva, ja ääretön.

Luonteva kysymys kuuluukin: ovatko kaikki äärettömät joukot numeroituvia?

Rationaalilukujen mahtavuus

Rationaalilukuja tuntuu olevan selvästi enemmän kuin kokonaislukuja, ja niiden numerointi vaikuttaa toivottomalta. Jo pelkästään lukujen 0 ja 1 välissä on äärettömän monta rationaalilukua.

Jos numerointia esimerkiksi aloittaa nollan jälkeen luvuista, joiden osoittaja on yksi, urakka ei tule koskaan valmiiksi: vaikkapa luku²₃ei ole listalla.

N 0 1 2 3 ...

Q 0 1 1

1 2

1 3 ...

Voidaan kuitenkin toimia ovelammin: kirjoitetaan positiiviset rationaaliluvut tau- lukkoon, jossa nimittäjät kasvavat alaspäin ja osoittajat oikealle:

1 1

2 1

3 1

4

1 ···

1 2

2 2

3 2

4

2 ···

1 3

2 3

3 3

4

3 ···

1 4

2 4

3 4

4

4 ···

... ... ... ... ...

Selvästi kaikki positiiviset rationaaliluvut ovat taulukossa. Aloittamalla oikeasta yläkulmasta ja valitsemalla sopiva reitti kaikki positiiviset rationaaliluvut saadaan numeroitua:

(22)

LUKU 4. LUVUT JA ÄÄRETTÖMYYS 1

1

2 1

3 1

4

1 ···

1 2

2 2

3 2

4

2 ···

1 3

2 3

3 3

4

3 ···

1 4

2 4

3 4

4

4 ···

... ... ... ... ...

Auki kirjoitettuna numerointi näyttää tältä, kun vielä annetaan nollalle pariksi nolla:

N 0 1 2 3 4 5 6 7 8 ...

Q 0 1 1

2 1

2 2

1 2

1 3

2 3

3 3

3 2 ...

Positiiviset rationaaliluvut on siis mahdollista numeroida! Itse asiassa jokainen positiivinen rationaaliluku esiintyy listalla äärettömän monta kertaa, esimerkiksi

11,²₂ja³₃ ovat sama luku. Tämä ei sinänsä ole ongelma, mutta jos halutaan laskea kukin luku vain kerran, kaksoiskappaleet voidaan jättää pois sitä mukaa kun niitä tulee vastaan. Silloin prosessi näyttää tältä:

1 1

2 1

3 1

4

1 ···

1 2

2 2

3 2

4

2 ···

1 3

2 3

3 3

4

3 ···

1 4

2 4

3 4

4

4 ···

... ... ... ... ...

Vastaavasti numerointi alkaa nyt näin:

N 0 1 2 3 4 5 6 7 8 ...

Q 0 1 1

2 1

1 2

1 3

2 3

3 2

3 1

4 1 ...

(23)

Tässä olivat vasta positiiviset rationaaliluvut, mutta negatiiviset saa numeroitua pienellä korjauksella. Voimme käyttää parilliset luonnolliset luvut positiivisten rationaalilukujen numerointiin ja parittomat negatiivisten. Lopullisen listan alku on alla.

N 0 1 2 3 4 5 6 7 8 ...

Q 0 −1 1

1 1 −2

1 2 1 −1

2 1 2 −1

3 1 3 ...

Rationaalilukuja on siis yhtä paljon kuin luonnollisia lukuja!

Huomautettakoon, että tämä päättely ei tuottanut laskukaavaa siitä, millä paikalla kukin rationaaliluku on listassa. Numeroituvuus saatiin kuitenkin perusteltua, joten laskukaava ei ole meille välttämätön.

Ylinumeroituvuus Kun tulokseksi on saatu

#N=#Z=#Q,

tekee mieli ajatella, että yksinkertaisesti kaikki äärettömät joukot ovat yhtä mahta- via. Yllättävää kyllä näin ei ole. Georg Cantor osoitti vuonna 1874, että reaalilukujen joukkoa ei voi numeroida. Alla esitettävässä todistuksessa käytetään Cantorin kuuluisaa diagonaaliargumenttia vuodelta 1891.

Väite. Välin ]0,1[ reaalilukuja ei voi numeroida.

Todistus. Tutkitaan välin ]0,1[ lukuja, eli lukujen 0 ja 1 välissä olevia reaalilukuja desimaaliesityksessä. Kuvitellaan, että ne on kaikki numeroitu jollakin tavalla:

N R

1 0,46874816...

2 0,21319856...

3 0,94813152...

4 0,33333333...

5 0,56218555...

... ...

Poimitaan nyt ensimmäiseltä riviltä ensimmäinen desimaali, toiselta riviltä toinen desimaali, ja niin edelleen. Poimituista desimaaleista muodostetaan uusi desimaaliluku. Lopuksi muutetaan jokainen desimaali seuraavasti: kaikki ykkö- set muutetaan kakkosiksi ja loput numerot ykkösiksi. Seuraava kuva selventänee asiaa.

(24)

N R

1 0,46874816...

2 0,21319856...

3 0,94813152...

4 0,33333333...

5 0,56218555...

... ...

⇒

^0,41838...

⇒

^0,12111...

Kysymys kuuluu, missä kohtaa alkuperäistä listaa uusi luku 0,12111... on?

• Se ei voi olla listan ensimmäinen luku, koska ensimmäinen desimaali on eri.

• Se ei voi olla listan toinen luku, koska toinen desimaali on eri.

• Se ei voi olla listan kolmas luku, koska kolmas desimaali on eri, ja niin edelleen.

Uusi luku 0,12111... ei siis voi olla listalla lainkaan! Alkuperäinen lista ei sisäl- tänytkään kaikkia väilin ]0,1[ reaalilukuja. Saman päättelyn voisi toistaa mille tahansa välin ]0,1[ reaalilukuja sisältävälle listalle, joten täydellistä listaa ei voi olla olemassa.

Reaalilukuja ei siis voi numeroida, ei edes välin ]0,1[ reaalilukuja. Tällaista joukkoa kutsutaan ylinumeroituvaksi. Lukujoukkojen mahtavuuksien vertailu päätyi seuraavaan, yllättävään lopputulokseen:

#N=#Z=#Q<#R.

Mahtavuuksien mielessä irrationaalilukuja on siis paljon enemmän kuin rationaalilukuja. Asiasta tekee erityisen hämmentävän se, että jokaisen kahden ratio- naaliluvun välissä on äärettömästi irrationaalilukuja, ja jokaisen kahden irratio- naaliluvun välissä on äärettömästi rationaalilukuja. Kuitenkin irrationaalilukujen mahtavuus on suurempi.

Huomautettakoon, että koska edellä kaikki yhdeksiköt muuttuivat ykkösiksi eivät- kä nolliksi, todistuksessa ei tarvitse murehtia sitä, että 1,0000... ja 0,9999... voivat tarkoittaa vain samaa lukua, kuten seuraavaksi perustellaan.

Mikä luku voisi olla 0,9999...?

Olisi mukavaa, jos jokaista desimaaliesitystä vastaisi yksi desimaaliluku. Loputto- maan määrään yhdeksikköjä päättyvät desimaaliesitykset ovat kuitenkin ongel- mallisia. Tarkastellaan esimerkiksi desimaaliesitystä 0,999...

(25)

Voidaan tietysti kysyä, onko tällaista lukua edes olemassa. Vaikka luvun voi merkitä paperille, se ei tarkoita että luku olisi hyvin määritely. Esimerkiksi ⁵₀ ei tarkoita mitään rationaalilukua, vaikka näyttääkin siltä.

Jos kuitenkin oletamme, että on olemassa hyvin määritelty lukux=0,999..., joka noudattaa desimaalilukujen laskulakeja, voimme laskea seuraavasti:

x=0,999... || ·10 10x=9,999...

Vähentämällä viimeinen yhtälö edellisestä saadaan 10x−x=9,999...−0,999...

9x=9 x=1.

Näin laskien saimme 0,999...=1, yllättävää! Jos siis haluamme puhua luvusta 0,999... tavallisia laskulakeja noudattavana desimaalilukuna, täytyy hyväksyä sen olevan yhtä suuri luvun 1 kanssa.

Toinen tapa päätyä samaan johtopäätökseen on laskea 0,999...=0,333...+0,333...+0,333...=1

3+1 3+1

3=1.

Emme yritä sanoa, että tämä asia olisi mitenkään yksinkertainen. Reaaliluku- jen täsmällinen määrittely onnistui vasta 1800-luvulla, vaikka niitä oli käytetty vuosisatoja.

Pohditaan asiaa vielä toisesta suunnasta: Luvun 0,999... voi ajatella summaksi 0,999...= 9

10+ 9 100+ 9

1000+ 9

10000+... ,

jossa on äärettömän monta yhteenlaskettavaa. Jos summa katkaistaann. termin kohdalta, saadaan

0,999...> 9 10+ 9

100+ ··· + 9 10ⁿ, eli toisin kirjoitettuna

0,999...>0,999...99

| {z }

nnumeroa

=1−0,000...01

| {z }

nnumeroa

=1− 1 10ⁿ. Lukujen 1 ja 0,999... erotuksesta voidaan siis sanoa

1−0,999...< 1 10ⁿ

kaikilla positiivisilla kokonaisluvuillan. Mikään positiivinen luku ei kuitenkaan ole pienempi kuin ₁₀¹n kaikilla luvunnarvoilla, sillä kunnkasvaa,₁₀¹n pienenee mielivaltaisen pieneksi. Lukujen 1 ja 0,999... erotus ei siis voi olla positiivinen, joten sen on oltava nolla, ja luvut 1 sekä 0,999... ovat siis sama luku.

(26)

LUKU 4. LUVUT JA ÄÄRETTÖMYYS Harjoitustehtäviä

Tehtävä 14. Osoita pareja muodostamalla, että parillisia luonnollisia lukuja on yhtä monta kuin luonnollisia lukuja yhteensä.

Tehtävä 15. Osoita pareja muodostamalla, että viidellä jaollisia kokonaislukuja on yhtä monta kuin luonnollisia lukuja.

Vihje s. 46→

Tehtävä 16. Osoita Cantorin diagonaaliargumenttia soveltaen, että ”sanoja”, jotka koostuvat vain kirjaimista a ja b, on ylinumeroituvan monta. Oletetaan, että sanat voivat olla äärellisen tai äärettömän pitkiä.

Vihje s. 46→

Tehtävä 17. Tutkitaan samoja ab-sanoja kuin edellisessäkin tehtävässä, mutta vaaditaan, että kaikkien sanojen tulee olla äärellisen mittaisia. Miksi tällaisten sanojen joukkoa ei voi todistaa ylinumeroituvaksi Cantorin diagonaaliargumentilla edellisen tehtävän tapaan? Onko kyseinen joukko numeroituva vai ylinumeroitu- va?

Tehtävä 18. Mitkä seuraavista joukoista ovat numeroituvia ja mitkä ylinumeroi- tuvia? Perustele kummassakin tapauksessa.

• Tason pisteet (x,y), missäxjayovat kokonaislukuja.

• Desimaaliluvut, joiden desimaaliesityksessä on vain numeroita 3 ja 0.

• Tason suorat, joiden yhtälöt ovat muotoa y =kx+b, missäk jab ovat kokonaislukuja.

Numeroituvuuden perusteluksi riittää jonkinlainen järjestelmällinen numeroin- titapa esimerkiksi kuvana esitettynä. Tässä ei tarvitse esittää laskukaavaa, joka kertoisi mikä järjestysluku kullekin joukon jäsenelle tulisi.

Tehtävä 19. Miksi rationaalilukujen joukkoa ei voi todistaa ylinumeroituvaksi Cantorin diagonaaliargumentilla? Rationaaliluvut kuitenkin voi esittää desimaali- lukuina siinä missä reaaliluvutkin.

(27)

5 Vaikeiden ongelmien ratkaiseminen

Matematiikan opiskelu on mainio tapa oppia ratkaisemaan vaikeita ongelmia.

Tämä kyky on suureksi hyödyksi myös muilla elämän aloilla. On mahdollista, että opintosi eivät ole valmentaneet sinua ratkaisemaan matemaattisia ongelmia, joiden ratkaisemiseen kuluu esimerkiksi kolme tuntia. Miten niitä pitäisi työstää?

Tässä on joitakin matemaattisiin ongelmiin liittyviä suuntaa antavia aikaskaaloja:

1 s – 100 s rutiinia kehittävä harjoitustehtävä matematiikan kirjassa 1 min – 60 min muutaman päättelyaskeleen vaativa harjoitustehtävä 15 min – 200 min vaikea tai muuten vain pitkä oppikirjatehtävä

1 h – 100 h kohtuullisen vaikea kilpamatematiikkatehtävä tai pulma muutama päivä helppo todellinen sovellusongelma

1 kk – 100 vuotta tutkimusongelma tieteessä tai teollisuudessa (ratkaisu koostuu lukuisten pienempien ongelmien ratkaisemisesta) yli 2000 vuotta Vieläkään ei tiedetä, onko parittomia täydellisiä lukuja

olemassa.

On selvää, että jos ongelma ei ratkea ilman tuntien työtä, sen selättäminen vaatii monipuolisia työtapoja ja aiempaa kokemusta vastaavista ongelmista. Kykysi ratkaista vaikeita ongelmia kehittyy parhaiten, kun työstät tämänhetkisten kykyjesi ylärajoilla olevia ongelmia.

Mikä tekee ongelmasta vaikean? Mahdollisia syitä voi olla monia:

• On epäselvää, mistä suunnasta ratkaisua pitäisi etsiä.

• On epäselvää, onko ratkaisua edes olemassa.

• On epäselvää, mitä täsmälleen yritetään saavuttaa.

• On epäselvää, onko tähän asti tehty työ lainkaan hyödyllistä.

Tällaisten ongelmien kanssa painiessa joutuu kestämään epävarmuutta ja ajoit- taista turhautumista, ja keskittymään intensiivisesti. Ne eivät ole huonoja taitoja oppia.

Miten harjaantunut matemaatikko sitten ratkoo vaikeita ongelmia? Tärkein vas- taus kuuluu: hyödyntämällä pitkää aiempaa kokemusta vastaavista ongelmista.

(28)

LUKU 5. VAIKEIDEN ONGELMIEN RATKAISEMINEN

Matemaatikon työhön sisältyy jatkuva uusien asioiden, alojen, tekniikoiden ja ideoiden opiskelu. Vuosien mittaan tästä kertyy melkoinen työkalupakki.

Asiantuntijan intuitio ohjaa kohti oikeita lähestymistapoja, ja intuitio kehittyy parhaiten kokemuksen kautta. Ongelmanratkaisijaksi tullaan siis ratkomalla ongelmia. On kuitenkin joitakin yleisiä lähestymistapoja, joista on hyvä olla tietoinen.

Ongelmanratkaisijan työkalupakki

Mitä tehdä, kun ratkaisu ei löydy heti?

• Tutustu.Leiki ongelman kanssa saadaksesi tuntumaa sen rakenteeseen.

Kokeile esimerkkejä. Piirrä kuva.

• Luo ja testaa hypoteeseja.Tee rohkeasti hypoteeseja eli olettamuksia: Voi- siko tämä kulma olla suora? Päteekö väite kaikilla alkuluvuilla? Voisivatko kaikki tarinan henkilöt puhua totta? Usein hypoteesia voi testata ilman, että ratkaisee koko tehtävän. Oli hypoteesi oikea tai väärä, se antaa ymmärrystä ongelman rakenteesta.

• Yksinkertaista.Esitä ongelmasta itsellesi yksinkertaisempi versio. Osaatko ratkaista sen? Voiko samalla tavalla ratkaista koko ongelman? Miksi ei?

Joskus harvoin on eduksi myös monimutkaistaa ongelmaa. Yleisempi tapaus voi olla helpompi ratkaista!

• Kirjoita ja piirrä. Kun aivoista yrittää narrata esiin oivalluksia, tarvitaan monipuolista aineistoa. Paperille piirtäminen on erittäin tehokas keino pitää asioita esillä ja hahmottaa niiden välisiä yhteyksiä. Lisäksi monet yksityiskohdat ovat liian monimutkaisia päässä pyöriteltäviksi.

• Vaihda näkökulmaa.Usein ensimmäiseksi yritetty lähestymistapa ei toimi. Kokeile siis monia! Jo ongelman kirjoittaminen eri muotoon voi antaa oivalluksen.

• Älä ole liian kriittinen.Paperille päätyy usein paljon toimimattomia ideoita ennen oikean löytymistä, mutta vain niin oikea idea löytyy.

(29)

Taikasaari

Tässä on esimerkki tehtävästä, jonka ratkaiseminen vaatii hieman työtä.

Taikasaari.Taikasaaren metsissä vaeltelee kolmenlaisia eläimiä: vuo- hia, susia ja leijonia. Sudet voivat syödä vuohia ja leijonat sekä vuohia että susia.

Koska kyseessä on Taikasaari:

• Jos susi syö vuohen, susi muuttuu leijonaksi.

• Jos leijona syö vuohen, leijona muuttuu sudeksi.

• Jos leijona syö suden, leijona muuttuu vuoheksi.

Nyt saarella on 17 vuohta, 55 sutta ja 6 leijonaa. Kuinka monta eläintä saarella korkeintaan on jäljellä siinä vaiheessa, kun kukaan ei voi enää syödä ketään?

Suosittelemme lukemaan Ville Tilviksen tätä ongelmaa käsittelevän artikkelin [15]

Solmu-lehdestä osoitteesta

https://matematiikkalehtisolmu.fi/2018/3/Taikasaari.pdf. Artikkelissa näet esimerkkejä ajattelutavoista, joilla tämän kaltainen ongelma voidaan ratkaista.

(30)

Harjoitustehtäviä

Tässä harjoitustehtäväsarjassa on joitakin ongelmia, jotka aukeavat vasta pienen pohdiskelun jälkeen. Tehtävien ratkomisjärjestyksellä ei ole suurta merkitystä.

Yritä löytää sopivia tapoja työstää ongelmia: kirjoita asioita ylös, piirrä kuvia, vaihda näkökulmaa, yksinkertaista.

Joka tehtävään on vihje sekä toinen vihje, ja niitä on tarkoitus myös käyttää. Jos olet 20 minuutin työskentelyn jälkeen jumissa, voi olla hyvä aika katsoa ensimmäinen vihje.

Tehtävät eivät ole kompia: kaikkiin on olemassa yksikäsitteinen ratkaisu.

Tehtävä 20. Yhteiset tekijät.Sijoita oheiseen 4×4-ruudukkoon positiivisia kokonaislukuja, kuhunkin ruutuun eri luku. Aina kun kahdella ruudulla on yhteinen sivu, ruutujen luvuilla täytyy olla ykköstä suurempi yhteinen tekijä. Vain yhteisillä sivuilla on merkitystä, nurkittain voi olla mitä lukuja hyvänsä.

Esimerkiksi luvut 12 ja 10 voivat olla vierekkäin, koska molemmat ovat jaollisia luvulla 2, eli toisin sanoen nillä on kummallakin tekijänä luku 2. Samoin luvut 10 ja 5 voivat olla vierekkäin, koska molemmat ovat jaollisia luvulla 5. Sen sijaan luvut 5 ja 12 eivät voi olla vierekkäin, koska niillä ei ole yhteisiä tekijöitä.

Täytä ruudukko siten, että suurin käyttämäsi luku on mahdollisimman pieni.

Kuinka pieneksi suurin luku on mahdollista saada? Perustele vastauksesi: mistä voit tietää, että kyseessä on minimi?

Tehtävä 21. Tanssiaiset.Suuressa ringissä seisoo 100 tanssijaa, jotka kaikki kat- sovat joko oikealle tai vasemmalle. Kaikki tanssijat, jotka näkevät vierustoverinsa kasvot, huutavat ”Hei!” Heitä on yhteensä 38. Tämän jälkeen kaikki tanssijat kään- tävät päänsä toiseen suuntaan ja huutavat taas ”Hei!”, jos näkevät vierustoverinsa kasvot. Kuinka moni huutaa ”Hei!” toisella kerralla?

(31)

Tehtävä 22. Hotellivieraat.Hotellissa on 100 huonetta, jotka on numeroitu luvuilla 1–100. Joka huoneessa on yksi asukas, ja he kaikki tapasivat aamiaisella.

Jokainen huoneiden 1–99 asukkaista kätteli huoneensa numeron verran eri ih- misiä. Kuinka montaa ihmistä huoneen 100 asukas kätteli? Kukaan ei kätellyt itseään.

Tehtävä 23. Sisarukset.Väestönlaskija koputti talon ovelle, ja avaamaan tuli mies.

Väestönlaskija kyseli miehen perheestä, jolloin tämä kertoi seuraavaa:

”Minulla on kolme tytärtä. Heidän ikiensä tulo on 72 ja summa sama kuin tämän talon numero.”

Väestönlaskija kävi tarkistamassa talon numeron ja palasi sitten neuvottomana:

”Olen laskenut ja laskenut, mutten tiedä, minkä ikäisiä tyttäresi ovat.”

”Ai niin!”, huudahti mies. ”Unohdin kertoa, että vanhin tyttäreni pitää jäätelöstä.”

”No sittenhän asia on selvä!” sanoi väestönlaskija ja kirjasi tyttöjen iät muistiin.

Kuinka vanhoja tytöt ovat?

Tehtävä 24. Sata vankia ja hehkulamppu.Tässä tarinassa sata elinkautisvankia kootaan saliin, jossa vankilan johtaja kertoo heille seuraavaa:

”Tunnin päästä teidät jaetaan sataan eristysselliin eri puolille vankilaa, ettekä enää näe toisianne. Kerran päivässä arvomme teistä satunnaisesti yhden (arpa voi osua samalle monta kertaa), joka viedään huoneeseen, jonka katossa on hehkulamppu.

Huoneeseen viety voi jättää valon päälle tai pois päältä. Seuraava vanki näkee lampun siinä tilassa, mihin se on edellisenä päivänä jätetty. Aluksi valo on poissa päältä.”

”Kun joku teistä onvarmasiitä, että kaikki vangit ovat käyneet lamppuhuoneessa ainakin kerran, hän saa ilmoittaa tämän ja kaikki pääsevät vapaaksi. Saatte kuitenkin vain yhden mahdollisuuden: jos ilmoittaja on väärässä, vietätte loppu- elämänne vankilassa.”

Vangeilla on tunti aikaa sopia strategiastaan ennen kuin heidät erotetaan toisis- taan. He sopivat, että ilmoittaa saa vain, kun on täysin varma siitä, että kaikki ovat käyneet lamppuhuoneessa.

Keksi keino, jolla vangit voivat ennemmin tai myöhemmin olla varmoja siitä, että kaikki ovat käyneet lamppuhuoneessa ainakin kerran.

Tämä tehtävä ei ole kompa, vaan tapa laskea sataan sääntöjen puitteissa on olemassa. Ainoa tapa viestiä on lamppu päällä / lamppu pois päältä. Mitkään muut yritykset (huutelu, seinäkirjoitukset, lampun rikkominen) eivät käy.

(32)

6 Lukujonot ja hyvinjärjestysperiaate

Tässä luvussa todistamme tuloksia, jotka puhuvat äärettömän monesta eri tapauksesta. Tälle on tarvetta vaikkapa lukujonojen yhteydessä.

Lukujono

Lukujonoon luettelo tietyssä järjestyksessä olevia lukuja, kuten positiivisten parillisten lukujen jono

2, 4, 6, 8, 10, 12, ...

Tämä lukujono on päättymätön, mutta lukujono voi olla myös päättyvä, kuten esimerkiksi yksinumeroisten alkulukujen jono 2, 3, 5, 7.

Lukujonossa esiintyviä lukuja kutsutaan jononjäseniksitaialkioiksi. Jäseniä mer- kitään usein pienillä kirjaimilla, joihin on alaindeksillä merkitty, kuinka mones jäsen on kyseessä. Esimerkiksi parillisten positiivisten kokonaislukujen jonossa voitaisiin merkitä

a1=2, a2=4, a3=6, ja niin edelleen.

Indeksointi antaa myös tavan määritellä tämä lukujono näppärästi: Lukujono koostuu luvuistaa_n, joille päteea_n=2n, missän>1 on kokonaisluku.Yleisen jäsenen kaavalla an=2·nvoidaan laskea vaikkapa, ettäa10=2·10=20.

Indeksointi voidaan aloittaa myös jostakin muusta kokonaisluvusta kuin yksi, kuten seuraavassa esimerkissä.

Esimerkki. Kuinka moni lukujononan=14−3n, missänon kokonaisluku ja n>0, jäsenistä on positiivinen?

Ratkaisu.Ongelman voi ratkaista kokeilemalla, sillä jonon jäsenet ovat sitä pie- nempiä, mitä suurempinon. Lasketaan:

a₀=14−3·0=14, a₃=14−3·3=5, a₁=14−3·1=11, a₄=14−4·3=2,

a2=14−3·2=8, a5=14−3·5= −1, negatiivinen.

Lukujono alkaa siis

14, 11, 8, 5, 2, −1, ...,

(33)

LUKU 6. LUKUJONOT JA HYVINJÄRJESTYSPERIAATE joten jonossa on viisi positiivista jäsentä.

Tämän ongelman olisi voinut ratkaista myös ratkaisemalla epäyhtälön 14−3n>0, josta saadaan

n<14 3 =42

3.

Tämän epäyhtälön toteuttavat indeksinnarvot 0, 1, 2, 3 ja 4, joten positiivisia jäseniä on viisi kappaletta.

Fibonaccin luvut ja rekursio

Lukujonon jäsenet voi määritellä myös viittaamalla sen aiempiin jäseniin elire- kursiivisesti. Hyvä esimerkki tästä on Fibonaccin lukujen jono

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...,

joka alkaa kahdella ykkösellä, minkä jälkeen jokainen jonon jäsen on kahden edellisen summa. Seuraava jonon jäsen olisi siis 55+89=144.

Nimensä Fibonaccin luvut ovat saaneet Leonardo di Pisan (n. 1170 – n. 1250) mukaan, sillä hänet tunnettiin myös nimillä Leonardo Bonacci ja Fibonacci. Ita- lialainen Fibonacci käytti lukuja kirjassaanLiber Abacilaskuongelmassa, jonka taustatarina liittyi kanien lisääntymiseen.

Fibonaccin luvut voidaan määritellä muodollisesti näin:









 F₁=1, F2=1,

F_n=F_n−1+F_n−2, kunn>^3.

Tässä siisF_non jokin Fibonaccin luku,F_n₋₁sitä edeltävä luku jaF_n₋₂sitä edeltävä.

Määritelmän kaavalla voidaan laskea

F3=F3−1+F3−2=F2+F1=1+1=2, F₄=F₄₋₁+F₄₋₂=F₃+F₂=2+1=3, F₅=F₅₋₁+F₅₋₂=F₄+F₃=3+2=5,

ja niin edelleen. Ajoittain on myös mukavuussyistä näppärää jatkaa jonoa vasemmalle päin asettamallaF₀=0, jolloin tietenkin myösF₀+F₁=0+1=1=F₂.

(34)

LUKU 6. LUKUJONOT JA HYVINJÄRJESTYSPERIAATE

Hyvinjärjestysperiaate

Koska haluaisimme pystyä todistamaan tuloksia, jotka puhuvat äärettömän monesta eri tapauksesta, otamme käyttöön seuraavan ilmeisen, mutta tärkeän, peri- aatteen:

Hyvinjärjestysperiaate.

Jokaisessa kokoelmassa positiivisia kokonaislukuja, joka sisältää ainakin yhden luvun, on olemassa pienin luku.

Tämä mahdollistaa asioiden todistamisen kaikille positiivisille kokonaisluvuille näin:

1. Tarkistetaan erikseen, että väite pätee pienimmillä luvunnarvoilla, kuten n=1, ja tilanteesta riippuen ehkä myösn=2, jan=3.

2. Oletetaan, että todistettava väiteeipidä paikkaansa kaikilla positiivisilla kokonaisluvuillan.

3. Silloin on olemassa positiivisia kokonaislukujan, joilla väite ei päde.

4. Voimme siis valita pienimmän positiivisen kokonaisluvunn, jolla väite ei päde.

5. Jos nyt voimme osoittaa, että tällä luvullanväitteen on kuitenkin pädettävä, saamme ristiriidan. Tämän perustelemisessa on yleensä oleellista se, että tehtyjen oletusten mukaan väite pätee pienemmissä tapauksissa.

6. Askeleen 5 ristiriita osoittaa, että alkuperäinen oletus siitä, että väite ei pidä paikkaansa kaikilla positiivisilla kokonaisluvuillan, on väärä. On siis todistettu, että väite pätee kaikilla positiivisilla kokonaisluvuillan.

Huomautus. Itse asiassa tämä menetelmä on oleellisilta osin sama asia kuin (matemaattisena) induktiona tunnettu todistusmenetelmä.

Pienin muutoksin menetelmällä voidaan todistaa myös väitteitä, jotka koskevat esimerkiksi kaikkia parillisia luonnollisia lukuja.

Esimerkki. Osoita, että jokaisella positiivisella kokonaisluvullanon 1+2+3+...+n=n(n+1)

2 .

(35)

Ratkaisu. Jos väite ei päde kaikilla positiivisilla kokonaisluvuillan, on oltava olemassa pienin positiivinen kokonaislukun, jolla

1+2+3+...+n6=n(n+1)

2 .

Väite toimii luvulla 1, sillä

1=1(1+1)

2 ,

joten on oltavan>1. Koskanon pienin luku, jolla väite ei päde, ja koskan>1, on väitteen on pädettävä luvullen−1, eli

1+2+...+(n−1)=(n−1)(n−1+1)

2 =(n−1)n

2 .

Tämän tiedon avulla voimme sieventää summaa 1+2+3+...+(n−1)+nseuraa- vasti:

1+2+...+(n−1)

| {z }

=⁽ⁿ⁻¹⁾ⁿ₂

+n=(n−1)n 2 +n=

µn−1 2 +1

¶ n=

µn−1 2 +2

2

¶

·n

=n+1 2 ·n

=n(n+1)

2 ,

mikä on ristiriidassa sen oletuksen kanssa, että väite ei päde luvullen. Siten ei voi olla pienintä lukuan, jolla väite ei pätisi, ja väitteen on pädettävä kaikilla positiivisilla kokonaisluvuillan.

Esimerkki. Osoita, että jokaisella positiivisella kokonaisluvullan pätee Fibo- naccin lukuja koskeva kaava

F₁+F₃+F₅+F₇+...+F_2n−1=F_2n.

Ratkaisu. KoskaF₁=1=F₂=F_2·1, kaava pätee kunn=1. Jos tulos ei pätisi joillakin positiivisilla kokonaisluvuilla, voisimme valita pienimmän positiivisen kokonaisluvunn>2, jolla väite ei pätisi. Koska lukunolisi pienin, jolla väite ei pätisi, se pätisi luvullan−1, eli olisi

F1+F3+...+F2(n−1)−1=F2(n−1),

ja voisimme sieventää alkuperäisen väitteen yhtälön vasenta puolta F₁+F₃+...+F_2(n−1)−1

| {z }

=F_2(n−1)

+F_2n−1=F_2(n−1)+F_2n−1=F_2n−2+F_2n−1=F_2n, mikä olisi vastoin luvunnmääritelmää. Siis ei voi olla olemassa pienintä positiivista kokonaislukuan, jolla väite ei päde, ja siten ei voi olla olemassa ainuttakaan sellaista lukua, eli väite pätee kaikillan.

(36)

LUKU 6. LUKUJONOT JA HYVINJÄRJESTYSPERIAATE Harjoitustehtäviä

Tehtävä 25. Todista kaikille positiivisille kokonaisluvuillenidentiteetti F1+F2+F3+...+Fn=Fn+2−1.

Tehtävä 26. Olkoonnpositiivinen kokonaisluku. Osoita, että 1+F₂+F₄+F₆+...+F_2n=F_2n+1.

Tehtävä 27. Osoita, että jokaisella positiivisella kokonaisluvullanpätee 1·2+2·3+3·4+...+n·(n+1)=n(n+1)(n+2)

3 .

Tehtävä 28. Osoita, että jokaisella positiivisella kokonaisluvullanpätee 1·2·3+2·3·4+3·4·5+...+n(n+1)(n+2)=n(n+1)(n+2)(n+3)

4 .

Huomautus:Tämän ja edellisen tehtävän tulokset vihjaavat, että vastaava kaava voisi toimia yleisemmin suuremmallakin määrällä peräkkäisiä kokonaislukuja.

Juuri näin asia onkin.

Vihje s. 50→

Tehtävä 29. Tehtävän 10 yleistys: Maassa onn>2 kaupunkia, ja jokaista kaupun- kiparia yhdistää rautatie. Kutakin rautatietä operoi joko yhtiö Blue Lines tai Red Lines. Osoita, että kaikista kaupungeista pääsee kaikkiin muihin kaupunkeihin käyttäen vain yhden yhtiön junia.

(37)

Tehtävä 30. Osoita, että kaikilla positiivisilla kokonaisluvuillanpätee F1F2+F2F3+F3F4+...+F2n−1F2n=F_2n² .

Tehtävä 31. Olkoonnpositiivinen kokonaisluku. Todista, että 1³+2³+3³+...+n³=n²(n+1)²

4 .

Tehtävä 32. Olkoonnpositiivinen kokonaisluku. Todista identiteetti 1²+2²+3²+...+n²=n(n+1)(2n+1)

6 .

Vihje s. 51→

Tehtävä 33. Määritellään lukujonoa₁,a₂, . . . asettamallaa₁=3,a₂=5, ja a_n+2=3a_n+1−2a_n

jokaiselle positiiviselle kokonaisluvullen. Etsi luvullea_nyksinkertainen luvunn lauseke. Todista, että lauseke on oikein kaikillan.

Tehtävä 34. Todista kokonaisluvuillen>2 identiteetti µ

1−1 4

¶ µ 1−1

9

¶ µ 1− 1

16

¶

···

µ 1− 1

n²

¶

=n+1 2n .

Tehtävä 35. Osoita, että jokaisella positiivisella kokonaisluvullanpätee 1

1·2·3+ 1

2·3·4+ 1

3·4·5+...+ 1

n(n+1)(n+2)=1 2

µ1

2− 1

(n+1)(n+2)

¶ .

Vihje s. 52→

(38)

Tehtävä 36. Määritellään lukujonoa0,a1,a2, . . . asettamalla a₀=0, a₁=1, a₂=2, a₃=6, sekä

a_n₊₃=2a_n₊₂+a_n₊₁−2a_n−a_n₋₁

jokaisella positiivisella kokonaisluvullan. Osoita, että lukuanon jaollinen luvulla njokaisella positiivisella kokonaisluvullan.

Tehtävä 37. Mitä seuraavassa ”lauseessa” ja sen ”todistuksessa” on vialla?

”Lause”.Kaikki maailman hevoset ovat keskenään samanvärisiä.

”Todistus.”Tarkastellaan hevosten joukkoja, joissa onnhevosta. Osoi- tetaan, että kaikilla luvunnarvoilla kunkin joukon hevoset ovat keske- nään samanväriset. Tapauksessan=1 kunkin joukon ainoa hevonen on itsensä kanssa samanvärinen, joten väite pätee.

Oletaan sitten, ettän>2 on pienin hevosten joukon koko, jolla väite ei päde. Tarkastellaan jotakinnhevosen joukkoa, jossa on hevoset h1,h2, . . . ,hn−1,hn. Koskanon pienin luku, jolla väite ei päde, kaikki n−1 hevosen joukot koostuvat keskenään samanvärisistä hevosista, ja erityisesti hevoseth₁, . . .h_n−1ovat keskenään samanväriset, samoin hevoseth2, . . .hn.

Koska joukoissa on samoja jäseniäh₂, . . . ,h_n−1, kaikki hevoseth₁,h₂, . . .h_novat keskenään samanvärisiä.

h₁ h₂ h₃ . . . h_n−1

l l l

h2 h3 . . . hn−1 hn

Lukunei siis ollutkaan pienin, joten sellaista lukua ei ole olemassa.

Kaikki maailman hevoset ovat siis keskenään samanvärisiä!

Tehtävä 38. Mitä seuraavassa ”lauseessa” ja sen ”todistuksessa” on vialla?

”Lause”.Jos a on positiivinen reaaliluku ja n positiivinen kokonaislu- ku, niin aⁿ⁻¹=1.

(39)

”Todistus.”Jos väite ei pätisi, olisi olemassa positiivinen kokonaisluku nja positivinen reaalilukuaniin, ettäaⁿ⁻¹6=1. Valitaannjaaniin, ettänon pienin mahdollinen. Koskaa¹⁻¹=a⁰=1, on oltavan>^2.

Mutta nyt myös, muistaen, ettänoli pienin mahdollinen arvo, jolla todistettava identiteetti ei päde,

aⁿ⁻¹=aⁿ⁻²·aⁿ⁻² aⁿ⁻³ =1·1

1 =1,

vastoin luvunnmääritelmää. Tämä ristiriita osoittaa, että alkuperäi- nen oletus siitä, että todistettava väite ei pitäisi paikkaansa, ei ole totta, ja siten olemme todistaneet väitteen.

Vihje s. 53→

Tehtävä 39. Mikä seuraavassa ”lauseessa” ja sen ”todistuksessa” on vialla?

”Lause”.Jokaisella positiivisella kokonaisluvulla n pätee 1

1·2+ 1 2·3+ 1

3·4+...+ 1

(n−1)n =3 2−1

n.

”Todistus”.Jos väite ei pätisi, niin olisi olemassa pienin positiivinen kokonaislukun, jolla väite ei pätisi. Koska tapauksessan=1

3 2−1

1=3

2−1=1 2= 1

1·2,

olisi varmastin>2. Mutta nyt luvunnmääritelmän nojalla olisi 1

1·2+ 1 2·3+ 1

3·4+...+ 1

(n−2)(n−1)=3 2− 1

n−1, ja voisimme laskea

1 1·2+ 1

2·3+ 1

3·4+...+ 1

(n−2)(n−1)+ 1 (n−1)n

=3 2− 1

n−1+ 1

(n−1)n =3 2− 1

n−1+ 1 n−1−1

n =3 2−1

n, vastoin luvunnmääritelmää. Siten ei ole olemassa pienintä lukuan, jolla väite ei pätisi, ja siten väite pätee kaikillan.

(40)

Tehtävä 40. Totea, että luvuille a=1+p

5

2 ja b=1−p 5 2

päteea²=a+1 jab²=b+1. Osoita sitten Binet’n kaava, jonka mukaan Fibonaccin luvuille pätee

F_n=aⁿ−bⁿ p5 jokaisella positiivisella kokonaisluvullan.

Tehtävä 41. Määritellään jonoa1,a2, . . . asettamalla a₁=1, a₂=1+1

1, a₃=1+ 1

1+¹₁, a₄=1+ 1 1+₁₊¹¹

1

, ...

Osoita, että jokaisella positiivisella kokonaisluvullanpätee a_n=F_n+1

Fn .

(41)

Huomautus tehtävien 40 ja 41 tuloksista.

Koska tehtävän 40 merkinnöillä|b| <1 ja|a| >1, suurilla luvunnarvoillabⁿon hyvin lähellä nollaa kun taasaⁿon huomattavan suuri luku. Tästä syystäF_non lähempänä ja lähempänä lukuaaⁿ/p

5, kunnkasvaa. Esimerkiksi F₅=5, F₁₀=55, F₁₅=610, ja F₂₀=6765, kun taas

a⁵

p5≈4,959675..., a¹⁰

p5 ≈55,003636..., a¹⁵

p5 ≈609,999672..., ja

a²⁰

p5≈6765,000030...

Raja-arvoja käyttäen tätä voitaisiin merkitä F_n∼ aⁿ

p5 tai F_n aⁿ/p

5−→1, kunn−→ ∞. KoskaFn∼aⁿ/p

5 suurillan, pätee tehtävän 41 merkinnöillä an=F_n₊₁

Fn ∼aⁿ⁺¹/p 5 aⁿ/p

5 =a, eli an∼a

suurillan. Tämä antaa aiheen määritellä ketjumurtolukukehitelmän

1+ 1

1+₁₊¹¹

1+1 ...

=1+p 5 2 .

Vasemmalla puolella olevan kaltaisia lausekkeita kutsutaan ketjumurtoluvuiksi, ja niille on olemassa varsin kaunis teoria. Lukua

a=1+p 5

2 ≈1,618034...

puolestaan kutsutaan kultaisen leikkauksen suhteeksi.

(42)

Ensimmäiset vihjeet

Luvun 2 ensimmäiset vihjeet

Tehtävän 1 vihje. Todistaaksesi 4×4-ruudukon laatoittamisen mahdolliseksi kannattaa vain ruveta piirtämään; ratkaisu löytyy todennäköisesti nopeasti.

Shakkilautaväritys voi olla avuksi 10×10-ruudukon kanssa.

←Tehtävä s. 12 Toinen vihje s. 55→

Tehtävän 2 vihje. Kuinka monta valkoista laattaa neliö peittää? Entä yksittäinen L-pala?

Tehtävän 3 vihje. Tässäkin olisi eduksi löytää sellainen väritys, jossa T-palat ja neliöpala peittäisivät ruutuja parillisuuden kannalta eri tavalla.

Tehtävän 4 vihje. Nyt shakkilautavärityksestä ei ole iloa. Helpointa voisi olla käyttää neljää eri väriä. Muitakin vaihtoehtoja toki on.

Tehtävän 5 vihje. Helpoin tapa todistaa laatoitus mahdolliseksi on piirtää se.

Kannattaa siis kokeilla muutama kerta eri tapoja.

Mahdottomaksi todistamisessa voisi auttaa esimerkiksi kaksivärinen väritys, jossa toista väriä on selvästi vähemmän.