todistukset

0

Ikä on vain numero

|

Koska maailma tuntuu siirtyneen faktojen jälkeiseen aikaan, myös täällä Pulmakulmassa lienee tarpeen venyttää totuuden rajoja. Osoitetaan matemaattista induktiota käyttäen, että kaikki suomalaiset ovat samanikäisiä.

Matemaattisessa induktioperiaatteessahan on kyse siitä, että jos voidaan osoittaa, että

  1. jokin luonnollisia lukuja tai jotain sen osajoukkoa koskeva väittämä pätee pienimmälle tarkasteltavalle luvulle, ja että
  2. väitteen totuudesta luvulle k seuraa väitteen totuus luvulle k+1,

niin tällöin väite pätee kaikille tarkasteltaville luvuille. Induktioperiaatteen hyvä havainnollistus löytyy esimerkiksi tästä.

No niin, sitten asiaan. Osoitetaan ensin, että yhden ihmisen joukossa kaikki ovat keskenään samanikäisiä. Tämä on tietenkin triviaalisti totta.

Tehdään seuraavaksi induktio-oletus, että k suomalaisen joukossa kaikki ovat samanikäisiä. Riittää osoittaa, että tästä seuraa se, että sattumanvaraisten k+1 suomalaisen joukossa kaikki ovat samanikäisiä. Tämä voidaan todistaa osoittamalla, että tämän joukon sattumanvaraiset henkilöt H ja S ovat samanikäisiä.

Poistetaan ensin k+1 suomalaisen joukosta henkilö H. Nyt jäljelle jääneet kaikki k suomalaista ovat induktio-oletuksen mukaan samanikäisiä. Siis S on samanikäinen kaikkien muiden kanssa, esimerkiksi henkilön M kanssa. Poistetaan seuraavaksi alkuperäisestä k+1 suomalaisen joukosta henkilö S. Nyt jäljelle jääneet k henkilöä ovat induktio-oletuksen mukaan samanikäisiä. Siis esimerkiksi H ja M ovat nyt samanikäisiä.

Mutta nythän toisaalta S ja M ovat samanikäisiä ja toisaalta H ja M ovat samanikäisiä, joten välttämättä H ja S ovat samanikäisiä. Olemme siis onnistuneet osoittamaan, että k+1 suomalaisen joukossa kaikki ovat samanikäisiä. Induktioperiaatteen mukaan kaikki suomalaiset ovat samanikäisiä!

No, tuota. Oikeasti minä en ole samanikäinen veljeni kanssa. Viikon vaikea pulma on selvittää, mikä meni pieleen. Onko matematiikka rikki?

Ratkaisu: Matematiikka ei onneksi ole rikki, vaan todistuksessa on ihan oikea virhe. Henkilöistä S ja H poikkeavan henkilön M olemassaoloa ei voida olettaa. Jotta näin voitaisiin tehdä, olisi pitänyt pystyä osoittamaan, että kaikissa kahden henkilön joukoissa on vain samanikäisiä. Ja tämähän ei tietenkään onnistu.

1

Peräkkäisten kokonaislukujen summa

|

Tämänkertainen pulmamme on kaksiosainen – viikon helppo ja viikon vaikea samassa paketissa. Löysin tämän lukuteoreettisen ongelman standup-matemaatikkona esiintyvän Matt Parkerin ensiluokkaisesta kirjasta Things To Make And Do In Fourth Dimension, ja se kuuluu seuraavasti.

Etsi lukujen 10 ja 20 väliltä ainoa kokonaisluku, jota ei voida esittää kahden tai useamman peräkkäisen positiivisen kokonaisluvun summana. Kun olet löytänyt sen, etsi sellainen (ainoa lajiaan, muuten) lukujen 30 ja 40 väliltä. Entä löydätkö lukujen 20 ja 30 väliltä tällaisia lukuja? Tässä lienee riittävästi purtavaa viikon helpon pulman tarpeisiin.

Vaikeampi pulma on tietenkin löytää kaikki sellaiset positiiviset kokonaisluvut, joita ei voida esittää peräkkäisten positiivisten lukujen summana. Entä miten tämä voidaan osoittaa?

Ratkaisu: Lukujen 10 ja 20 väliltä ainoa luku, jota ei voida esittää kahden tai useamman peräkkäisen luvun summana on 16. Lukujen 30 ja 40 väliltä löytyy tällaisista luvuista luku 32. Lukujen 20 ja 30 välillä ei tällaisia lukuja ole. Onko tässä vinkkiä tarpeeksi? Kyllä vain: kaikki muut luvut voidaan esittää peräkkäisten lukujen summina paitsi kakkosen potenssit. Todistetaan tämä:

Aloitetaan yksinkertaisesti. Kaikki parittomat luvut voidaan esittää muodossa 2n+1, missä n on jokin kokonaisluku. Tämä tarkoittaa heti sitä, että pariton luku voidaan ilmoittaa muodossa n+(n+1), eli kahden peräkkäisen luvun summana.

Siirrytään sitten parillisiin lukuihin. Jos luku on jaollinen kolmella, se voidaan ilmoittaa muodossa 3n, missä n on kokonaisluku. Toisaalta

    \[3n=(n-1)+n+(n+1),\]

joten kaikki kolmella jaolliset luvut voidaan esittää kolmen peräkkäisen luvun summana. Itse asiassa on helppo huomata, että

    \[5n=(n-2)+(n-1)+n+(n+1)+(n+2),\]

ja että sama idea yleistyy välittömästi kaikille muillekin parittomalla luvulla jaollisille kokonaisluvuille. Näin on saatu katettua jo kaikki muut luvut paitsi kakkosen potenssit (sillä kaikissa muissa parillisissa luvuissa on jokin pariton luku tekijänä). Nyt on osoitettava enää, että mitään kakkosen potensseja ei todellakaan voida kirjoittaa peräkkäisten lukujen summaksi.

Tutkitaan yleisesti k peräkkäisen kokonaisluvun summaa. Jos lukuja on pariton määrä, on summa jaollinen jollakin parittomalla luvulla, kuten edellä todettiin. Tutkitaan siis yleistä peräkkäisten lukujen summaa, jossa on parillinen määrä summan tekijöitä. Jos ensimmäinen luvuista on m, on viimeinen niistä m+(k-1). Saadaan aritmeettinen summa

    \[m+(m+1)+(m+2)+\cdots +(m+(k-1))\]

    \[=km+(0+1+2+\cdots +(k-1))\]

    \[=km+\frac{k}{2}(k-1).\]

Lavennetaan ensimmäistä termiä kakkosella ja otetaan osoittajasta k yhteiseksi tekijäksi. Saadaan

    \[km+\frac{k}{2}(k-1)=\frac{k(2m-k-1)}{2}.\]

Koska k on parillinen kokonaisluku, on tulon tekijä (2m-k-1) varmasti pariton, joten saatu luku ei voi olla kakkosen potenssi. Näin ollen kakkosen potensseja ei voida milloinkaan esittää peräkkäisten lukujen summana.