Kiinatehtävä, osa 2

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

Kiinan IMO-joukkueen valintakoe 5, 2010, tehtävä 3

Olkoon $k$ positiivinen kokonaisluku. Osoita, että on olemassa sellainen positiivinen kokonaisluku $N$, niin että kaikilla $n \ge N$ luvulla ${n \choose k}$ on vähintään $k$ erisuurta alkutekijää.

Ratkaisu

Ohessa ratkaisu, joka on lähes suoraan ajatuskulkuni tehtävää ratkoessani. Tästä syystä ratkaisu sisältää joitakin “turhia” osioita. Ratkaisussa käytetään varsin yleistä ja hyödyllistä notaatiota: $v_p(n)$ on suurin $p$:n potenssi, joka jakaa luvun $n$. Toisin sanoen, $p^{v_p(n)} \mid n$, mutta $p^{v_p(n) + 1} \nmid n$.

Tehdään yksinkertaisuuden vuoksi sijoitus $n = m + k$. Nyt, tutkittavana on luku

$$\frac{(m+k)(m+k-1)\ldots (m+1)}{k!}$$

Jos tällä luvulla on alle $k$ erisuurta alkutekijää, tulee yhtälön

$$(m+k)(m+k-1)\ldots (m+1) = k! p_1^{a_1}p_2^{a_2} \ldots p_{k-1}^{a_{k-1}} \ (1)$$

päteä jollain alkuluvuilla $p_i$ ja epänegatiivisilla kokonaisluvuilla $a_i$. Alkuperäinen tehtävänanto on ekvivalentti seuraavan väitteen kanssa:

Yhtälöllä $(1)$ on ratkaisu vain äärellisen monella $m$.

On suhteellisen helppoa huomata, että yhtälöllä ei ole kovin montaa ratkaisua, jos $p_i > k$ kaikilla $i$. Tämä johtuu seuraavasta havainnosta:

Jos $p_i \mid m + a$ ja $p_i \mid m + b$, niin $p_i \mid a - b$.

Siis jos kaikki $p_i$:t olisivat suuria, tulisi olla olemassa jokin $a$, jolla $p_i \nmid m + a$ kaikilla $i$. Tämän seurauksena luvulla $m + a$ ei tule olla mitään lukua $k$ suurempia alkutekijöitä, sillä muuten jokin alkuluku $p > k$, $p \neq p_i$ jakaisi yhtälön $(1)$ vasemman puolen, muttei oikeaa. Samoin nähdään myös, että jos $p \mid m + a$, niin $p$:n eksponentin tulee olla enintään $v_p(k!)$. Täten tulee olla $m + a \le k!$, eli $m \le k!$.

Mutta entä sitten, jos $p_i \le k$ jollain $i$? Voisimme silti yrittää soveltaa aiemmin esitettyä ideaa: osoitimme aiemmin, että on olemassa jokin $a$, jolla $p_i \nmid m + a$ kaikilla $i$. Nyt emme pysty aivan samaan, mutta huomaamme kuitenkin, että kovin suuri $p_i$:n potenssi ei voi jakaa lukua $m + a$, kaikilla $a$, jollain $i$. Paremmin muotoiltuna:

Lemma 1

Käytetään yhtälön $(1)$ merkintöjä. On olemassa jokin $a$ jolla pätee seuraava väite: $p_i^c \nmid m + a$ kaikilla $i$, jollain luvusta $k$ riippuvalla vakiolla $c$.

Tämän väitteen todistus on suhteellisen intuitiivinen.

Todistus

Olkoon $p \in \lbrace p_1, p_2, \ldots , p_{k-1} \rbrace $. Olkoon $m + b$ se luku joukosta $\lbrace m+1, m+2, \ldots , m+k \rbrace $ jolla $v_p(m + b)$ on maksimaalinen (jos vaihtoehtoja on monta, valitaan mikä vain). Tällaisia $b$ on yhteensä enintään $k-1$, kun $p$ käy läpi kaikki joukon $\lbrace p_1, \ldots , p_{k-1} \rbrace $ alkuluvut. Täten on olemassa jokin luku $a$, jolla $v_p(m + a)$ ei ole millään $p \in \lbrace p_1, p_2 \ldots , p_{k-1} \rbrace $ tällainen maksimaalinen luku.

Pidetään $p$ vakiona. Merkitään $v_p(m + b) = t$. Pyritään nyt saamaan jokin yläraja luvulle $v_p(m + a)$, $a \neq b$.

Mikä on niiden lukujen määrä välillä $[m+1, m+k]$ joiden tekijänä on luku $p^u$, missä $u \le t$ on vakio? Tämä määrä on tietysti enintään $\lceil \frac{k}{p^u} \rceil$. Jos jätämme huomiotta luvun $n + b$, on näiden lukujen määrä enintään $\lfloor \frac{k}{p^u} \rfloor \le \frac{k}{p^u}$. Siispä, pätee

$$v_p((m+1)(m+2) \ldots (m+b-1)(m+b+1)\ldots (m+k)) \le$$ $$\frac{k}{p} + \frac{k}{p^2} + \ldots + \frac{k}{p^u} \le \frac{k}{p-1}$$

Tässä ensimmäinen epäyhtälö seurasi aiemmasta päättelystä luvun $p$ potenssien esiintymisestä välin $[m+1, m+k]$ lukujen tekijöinä, ja jälkimmäinen epäyhtälö seurasi geometrisen summan kaavasta.

Tästä seuraa, että lemman halutuksi vakioksi $c$ kelpaa $k+1$, sillä $p \ge 2$ kaikilla alkuluvuilla $p$.

Ratkaisun viimeistely

Tutkitaan nyt lukua $m + a$. Se ei voi olla enää kovin suuri: se ei ole jaollinen millään alkuluvulla, joka olisi suurempaa kuin $k$. Lemman nojalla se ei myöskään ole jaollinen kovin suurilla alkuluvun potensseilla. Tarkemmin:

Olkoon $p$ jokin alkuluku väliltä $[1, k]$. Mikä on sen suurin mahdollinen potenssi $p^u$ joka jakaa luvun $m + a$? Tutkitaan erikseen kahta tapausta

1. $p \in \lbrace p_1, p_2, \ldots p_{k-1} \rbrace $. Lemman nojalla pätee $u \le k$.

2. $p$ ei kuulu joukkoon $\lbrace p_1, p_2, \ldots p_{k-1} \rbrace$ Tällöin suurin $p$:n potenssi, joka jakaa yhtälön $(1)$ vasemman puolen on sama kuin suurin potenssi, joka jakaa yhtälön oikean puolen. Tämä on $v_p(k!) \le k$.

Siis $v_p(m+a) \le k$ kaikilla $p \in [1, k]$.

Täten, $m + a \le 1^k \cdot 2^k \cdot 3^k \cdot \ldots \cdot k^k = k!^k$. Tämä pätee kaikilla ratkaisuilla $m$. Olemme näin ollen saaneet ylärajan luvulle $m$, jos haluamme, että luvulla ${m + k \choose k}$ on alle $k$ alkutekijää. Tämä todistaa väitteen.