Kiinatehtävä, osa 1

$\newcommand{\pyj}{\mathop{\rm pyj}}\newcommand{\syt}{\mathop{\rm syt}}$

Tässä postauksessa käsitellään seuraavan tehtävän ratkaisu:

Kiinan IMO-joukkueen valintakoe 4, 2010, tehtävä 3 Olkoon $f(n)$ luvun $n$ itseään pienempien tekijöiden summa, esimerkiksi $f(10) = 1 + 2 + 5$. Määritellään $f^1(n) = f(n)$, ja $f^i(n) = f^{i-1}(f(n))$ kaikilla $i > 1$.

Olkoon annettu $k \in \mathbb{N}$. Osoita, että on olemassa $n \in \mathbb{N}$, jolla

$$n < f(n) < f^2(n) < \ldots < f^k(n)$$

Ennen kuin mennään tehtävän ratkaisuun, lukijan olisi hyvä miettiä tehtävää ainakin muutama minuutti käsittääkseen mistä todella on kyse.

Ratkaisua varten lukijan oletetaan tuntevan Dirichlet’n lause ja tekijäfunktion perusominaisuudet.

Huomautettakoon vielä, että on avoin ongelma, onko olemassa sellaista $n \in \mathbb{N}$, jolla toteutuisi ääretön epäyhtälöketju $n < f(n) < f^2(n) < \ldots$.

Ratkaisu Olkoon $\sigma(n)$ luvun $n$ tekijöiden summa, siis $\sigma(n) = f(n) + n$.

Lemma 1. Jos $n = 6k$, missä $\syt(k, 6) = 1$, $k > 1$, niin $n < f(n)$.

Todistus Pätee $\sigma(n) = \sigma(6) \sigma(k) = 12\sigma(k) > 12k = 2n$. Täten $f(n) = \sigma(n) - n > n$.

Lemma 2. Olkoon $p$ alkuluku. Jos $p \equiv 2 \pmod{3}$, $p \mid n$, $p^2 \nmid n$, niin $\sigma(n)$ on jaollinen kolmella.

Todistus Olkoon $n = pm$, missä $\syt(p, m) = 1$. Nyt $\sigma(n) = \sigma(p)\sigma(m) = (p+1)\sigma(m)$. $p + 1$ on jaollinen kolmella.

Nyt, valitaan tehtäväämme $n = 6p_1p_2 \ldots p_k \cdot a_0$, missä $p_i$:t ovat kolmea suurempia erisuuria alkulukuja. Lisäksi valitaan $\syt(6p_1p_2\ldots p_k, a_0) = 1$. Valitaan vielä $p_i$:t seuraavasti:

$p_1 \equiv 2 \pmod{3}$

$p_{i+1} \equiv -1 \pmod{p_i^2}$ kaikilla $i \ge 1$

Tämä valinta on mahdollinen Dirichlet’n lauseen nojalla.

Väite $f^t(n) = 6p_1p_2\ldots p_{k-t}a_t$, kaikilla $0 \le t \le k$, missä $\syt(6p_1p_2\ldots p_{k-t}, a_t) = 1$.

Väitteen todistus Todistetaan väite induktiolla. Voimme sanoa, että väite pätee, kun $t = 0$ määrittelemällä $f^0(n) = n$ (jos lukija ei ole tyytyväinen tähän, voidaan tapaus $t = 1$ todistaa täysin vastaavasti kuin alla oleva induktioaskel).

Oletetaan, että väite pätee arvolla $t$, ja osoitetaan, että se pätee arvolla $t+1$.

$$f^{t+1}(n) = f(f^{t}(n)) = f(6p_1p_2\ldots p_{k-t}a_t) =$$ $$\sigma(6p_1p_2 \ldots p_{k-t}a_t) - 6p_1p_2\ldots p_{k-t}a_t =$$ $$6(2\sigma(p_1p_2 \ldots p_{k-t}a_t) - p_1p_2\ldots p_{k-t}a_t)$$

Merkitään $b_{t+1} = 2\sigma(p_1\ldots p_{k-t}a_t) - p_1p_2\ldots p_{k-t}a_t $ Jotta saamme induktioaskeleen läpi, tulee meidän osoittaa seuraavat asiat:

1. $\syt(b_{t+1}, 6) = 1$
2. $p_i \mid b$ kaikilla $i < k - t$
3. $p_i^2 \nmid b$ kaikilla $i < k - t$

Edetään järjestyksessä. Asiaa 1 varten huomataan, että luku $b_{t+1}$ on selvästi pariton, sillä $p_i$:t ja $a_t$ ovat kaikki parittomia. Lisäksi luku $\sigma(p_1p_2\ldots p_{k-t}a_t)$ on jaollinen kolmella (sovelletaan lemmaa 2 alkuluvulla $p_1$).Täten $b_{t+1}$ on kolmella jaollisen ja kolmella jaottoman luvun erotus, eli se ei ole jaollinen kolmella.

Listan toinen ehto pätee, sillä $2\sigma(p_1\ldots p_{k-t}a_t)$ on jaollinen luvulla $\sigma(p_{i+1}) = p_{i+1} + 1 \equiv 0 \pmod {p_i^2}$ kaikilla $i < k - t$. Siis $p_i$ jakaa $\sigma$-lausekkeen, sekä tulon $p_1p_2\ldots p_{k-t}a_t$, joten $p_i$ jakaa luvun $b_{t+1}$.

Kolmannen ehdon pätevyys huomataan edellisestä: saamme oikeastaan, että $p_i^2$ jakaa $\sigma$-lausekkeen. $p_i^2$ ei kuitenkaan jaa lukua $p_1p_2\ldots p_{k-t}a_t$, joten se ei jaa lukua $b_{t+1}$.

Voimme siis merkitä $a_{t+1} = \frac{b_{t+1}}{p_1p_2\ldots p_{k-t}}$ Edellisten toteamusten nojalla kaikki induktioväitteessä halutut asiat toteutuvat nyt myös luvulle $a_{t+1}$. Induktioaskel on otettu ja väite on tosi.

Tehtävänannon väite seuraa nyt suoraan edellisestä väitteestä. Lemman 1 nojalla pätee $f^{t+1}(n) > f^t(n)$ (sovelletaan lemmaa arvolla $f^t(n)$). Olemme valmiit.

Motivaatio ratkaisun takana Ratkaisu ei välttämättä näytä kovin vaikealta, mutta se voi olla vaikea keksiä. Miten keksitään valita $n$, joka on muotoa $6p_1p_2\ldots p_k \cdot a_0$? Pyrin selittämään, mistä ratkaisun ideat on vedetty.

Todetaan ensiksi, että koitin ensin monia muita ideoita, jotka eivät toimineet. Keksin mm. kaksi erilaista ratkaisua olettaen joko Goldbachin konjektuurin tai parillisten täydellisten lukujen äärettömyyden todeksi. (Harjoitustehtävä: keksi ratkaisu olettaen jompikumpi edellä olevista konjektuureista todeksi). Toimivan ratkaisun keksimiseen kului toistakymmentä tuntia.

Pyrin ensin keksimään, millaisilla $n$ voisi päteä $n < f(n)$. Tästä saadaan helposti lemma 1. Valitaan siis $n$ olemaan muotoa $6k$, $\syt(6, k) = 1$. Ideana oli sitten valita $n$ niin, että myös luku $f(n)$ olisi muotoa $6t$, missä $\syt(6, t) = 1$. Miten tämä onnistuisi? Tiedämme, että

$f(n) = f(6k) = 6(2\sigma(k) - k)$

Haluamme, että luvuilla $2f(k) - k$ ja $6$ ei ole yhteisiä tekijöitä. Sillä $k$ on pariton, tulee enää vain huolehtia kolmella jaollisuudesta. Tähän riittää valita lemman 2 ilmoittama alkutekijä $p_1$ luvulle $k$.

Mutta miten voisimme jatkaa näin? Kaikki on hyvin niin kauan, kunhan myös $f(n)$ on jaollinen alkuluvulla $p_1$. Tästä saamme idean: voimme valita $n$:lle toisen alkutekijän $p_2$, joka “suojelee” alkutekijää $p_1$. $p_2$ suojelee alkutekijän $p_1$ esiintymistä, jos $p_2 \equiv -1 \pmod{p_1^2}$. Voimme edelleen valita luvulle $p_2$ suojelijan $p_3$, ja näin edespäin. Tästä saamme kokonaisen ratkaisun.