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

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.

2

Uusi vuosi

Kuva: Maria Morri/Flickr (CC BY-SA 2.0)

Kuva: Maria Morri/Flickr (CC BY-SA 2.0)

Vuoden 2016 alku tarkoitti binäärilukuna hauskannäköistä siirtymää vuodesta 11111011111 vuoteen 11111100000.

On myös olemassa tapoja esittää luku 2016 vain yhtä numeroa ja joitakin laskutoimitussymboleja käyttäen. Koska 2016=2^5\cdot 3^2\cdot 7, on se jaollinen muiden muassa luvuilla 2, 3, 6, 7 ja 9, joten se voidaan totta kai kirjoittaa tylsästi esimerkiksi 3+3+3+\cdots riittävän monta kertaa. Tämän viikon vaikeana kysytään kuitenkin hieman kiehtovampaa tapaa esittää luku 2016.

Pystytkö esittämään luvun 2016, jos käytettävissäsi on vain yksi numero korkeintaan viisi kertaa sekä mitä tahansa laskutoimitussymboleja? Tai pystytkö keksimään jonkin muun kuin pelkkään yhteenlaskuun perustuvan tavan hyödyntää yhtä yksinumeroista lukua?


 

Ratkaisu: Uusi vuosi on aina numeronikkareille uusi hauska haaste. Kuinka ollakaan, suosikkimatemaatikkoihini kuuluva Alex Bellos kysyi vuoden 2016 rakentelemista The Guardianin palstallaan. Sieltä löytyi esittämääni ongelmaan vaihtoehtoinen ratkaisu, jota en ollut itse ajatellut. Nimittäin Bellosin ratkaisu on 2016=(4+4)\cdot(4^4-4).

Itseäni silti naurattaa vielä enemmän alkuperäinen löytöni uudenvuodenyöltä Twitteristä. Pelleilläänpä vähän binomikertoimilla. Nyt huomataan, että \binom{64}{2}=2016. Edelleen 2^6=64 ja \binom{4}{2}=6 ja vielä 2^2=4. Pysyttekö mukana? Tästä saadaan riemukkaasti, että

    \[2016=\binom{2^{\binom{2^2}{2}}}{2}.\]

Alex Bellos kysyi myös sitä, kuinka vuosi 2016 voitaisiin esittää lukujen 10, 9, 8, 7, 6, 5, 4, 3, 2 ja 1 avulla. Hän sai valtavasti vastauksia, joista hillittömin oli Sebastian Radun vastaus:

    \[2016=[(10\sqrt{9}\cdot 8! / 7) \quad (\mbox{modulo }6^5)] + 4!\cdot 3!\cdot 2! + \arccos 1.\]

Hyvää uutta vuotta 2016 toivoo Opettaja H:n pulmakulman henkilökunta.

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.