Našou úlohou je dokázať, že pre každú podmnožinu ${ 1, 2, \dots, 2018 }$ existuje číslo $n$ také, že $a_k(n)$ je štvorec len pre $k$ z vybranej podmnožniny. Inak povedané, že existuje $2^{2018}$ čísel (pre každú podmnožinu jedno) $n_1,\, n_2,\, \dots,\, n_{2^{2018}}$ takých, že pozície, na ktorých sú štvorce v postupnostiach $a_1(n_i),\, a_2(n_i),\, \dots,\, a_{2018}(n_i)$ sú pre rôzne $i$ rôzne. Chceme nájsť také $n_i$-ká.

Pozrime sa ešte raz na množinu ${ 1, 2, \dots, 2018 }$. Je číslo $2018$ niečím špeciálne? Pravdepodobne nie. Úloha zo zadania by asi mohla byť zadaná pre hocijakú množinu ${1, 2, \dots, m }$. Na dokázanie úlohy pre $m=2018$ si môžeme skúsiť pomôcť dokázaním úlohy pre menšie hodnoty (pre ne by to mohlo ísť tiež dokázať). Inak povedané, môžeme skúsiť použiť matematickú indukciu[^1]. Ako použiť indukciu zatiaľ netušíme, potrebujeme si najprv niečo o súčinoch deliteľov zistiť.

Majme číslo $n$. Poďme zrátať súčin jeho deliteľov. Keď si vypíšeme deliteľov $n$, tak si môžeme všimnúť, že súčin najmenšieho a najväčšieho deliteľa je $n$, druhého najmenšieho a druhého najväčšieho deliteľa je $n$, tretieho najmenšieho a tretieho najväčšieho deliteľa je $n \dots$ To platí aj všeobecne, ku každému deliteľovi $d$ existuje aj deliteľ $\frac{n}{d}$ (teda okrem prípadu, že $n=x^2$, vtedy by deliteľ $x$ mal tvoriť pár sám so sebou). Vynásobením párov dohromady dostávame $$D(n)=n^{\text{(počet deliteľov n)}/2}$$ (rozmyslite si, že to platí aj keď je $n$ štvorec).

Teda pre dané $n$ sa bude postupnosť $a_1(n),\, a_2(n),\, \dots,\, a_{2018}(n)$ skladať z nejakých mocnín čísla $n$. Aby sme našli čo najjednoduchšie $n$-ká, tak by sme ich mohli hľadať ako mocniny prvočísla. Akého prvočísla nám môže byť jedno (počty deliteľov to neovplyvní), preto si zoberme za prvočíslo $2$, dostaneme čísla v tvare $2^t$. Číslo $2^t$ má deliteľov $1,\, 2,\, 4,\, \dots,\, 2^t$, ich súčin je $2^{t(t+1)/2}$, platí $a_2(2^t)=D(2^t)=2^{t(t+1)/2}$.

To, či je $2^s$ štvorec závisí od parity $s$ ($2^{2s’}$ je štvorec, ale $2^{2s’+1}$ nie). Pozrime sa na postupnosť $a_i(2^t)$:

• $a_2=D(2^t)$ je štvorec práve vtedy, keď je číslo $t(t+1)/2$ párne. Kedy to nastáva, závisí od zvyšku $t$ po delení $4$.

• Kedy je $a_3=2^{a_2(2^t)(a_2(2^t+1))/2}$ štvorec, závisí od zvyšku $a_2(2^t)$ po delení $4$.

• Kedy je $a_4=2^{a_3(2^t)(a_3(2^t+1))/2}$ štvorec, závisí od zvyšku $a_3(2^t)$ po delení $4$.

Toto pozorovanie možno zovšeobecniť, ale to nám samo o sebe nepomáha hľadať $n$-ká. Napovedá nám to však, že by mohlo mať zmysel uvažovať zvyšky $t$ po delení $2^s$. Možno si uvedomiť, že ak $t$ a $t’$ rovnaký dávajú rovnaký zvyšok po delení $2^s$, tak exponenty členov $a_2(2^t)=D(2^t)$ a $a_2(2^{t’})=D(2^{t’})$ dávajú rovnaký zvyšok po delení $2^{s-1}$, exponenty členov $a_3(2^t)=D(D(2^t))$ a $a_3(2^{t’})=D(D(2^{t’}))$ dávajú rovnaký zvyšok po delení $2^{s-2}…$ Teda $a_i(2^t)$ aj $a_i(2^{t’})$ (pre $i$ od 1 do $s$) sú štvorce buď obe súčasne, alebo ani jedno.

Toto tvrdenie by sme mohli použiť spolu s matematickou indukciu. Preto by sa nám hodilo tipnúť si vyhovujúce $n_i$-ká pre množinu ${2^1,2^2,2^3,\dots, 2^{2^m}}$. Ak je $m=1$, tak sú pozície štvorcov v postupnostiach $a_i(n)$ pre $n=1,2$ rôzne. Ak je $m=2$, tak sú pozície štvorcov v postupnostiach $a_i(n)$ pre $n=2^1,\,2^2,\,2^3,\,2^4$ rôzne. Pre $m=3$ sú vhodné $n$: $2^1,\,2^2,\,2^3,\,2^4,\,2^5,\,2^6,\,2^7,\,2^8$. Pre nejaké $m$ by mohli byť vyhovujúce $n_i$: $2^1,\, 2^2,\, \dots,\, 2^{2^{m}}$. Poďme to dokázať.

Budeme postupne dokazovať, že pozície štvorcov v postupnostiach $a_1(n),\, a_2(n), \,\dots,\, a_m(n)$ pre $n$ z množiny ${2^1, 2^2, 2^3, \dots, 2^{2^m} }$ sú rôzne. Prvý krok: pre $m=1$ a množinu ${2^1, 2^{2^1}}$. Postupnosti $a_1(n),\, \dots,\, a_m(n)$ sú jednoprvkové, číslu $2^1$ prislúcha postupnosť $2$ (čo nie je štvorec), číslu $2^2$ prislúcha postupnosť $4$ (čo je štvorec).

Indukčný krok: ideme dokázať, že postupnosti pre $n$ z množiny ${2^1, 2^2, 2^3, \dots, 2^{2^m} }$ sú rôzne. Z indukčného predpokladu vieme, že pozície štvorcov v postupnostiach $a_1(n), a_2(n), \dots, a_{m-1}(n)$ pre $n$ z množiny ${2^1, 2^2, 2^3, \dots, 2^{2^{m-1}} }$ sú rôzne. Indukčným krokom nám pribudli $n$-ká: $2^{2^{m-1}+1},\, 2^{2^{m-1}+2},\, 2^{2^{m-1}+3},\, \dots,\, 2^{2^m}$. Keďže pribudnuté číslo $2^{2^{m-1}+x}$ má rovnaký zvyšok exponentu po delení $2^{m-1}$ ako exponent $2^x$, pozície štvorcov na prvých $m-1$ miestach majú postupnosti $a_i(2^x)$ aj $a_i(2^{2^{m-1}+x})$ rovnaké, preto sú postupnosti čísel $2^{2^{m-1}+1},\, 2^{2^{m-1}+2},\, 2^{2^{m-1}+3},\, \dots,\, 2^{2^m}$ rôzne (líšia na prvých $m-1$ pozíciach). Potrebujeme ešte ukázať, že novo pribudnutým číslam $n$ prislúchajú iné postupnosti $a_i(n)$ ako pôvodným číslam. T. j., ak sa pozície štvorcov dvoch čísel $n_1$ a $n_2$ zhodujú na prvých $m-1$ pozíciach, tak sa budú líšiť na $m$-tej. Z toho, čo sme doteraz ukázali musí platiť, že $n_1$ a $n_2$ sú postupne $2^t$ a $2^{t+2^{m-1}}$ (pre $t$ do $2^{m-1}$).

Dokázať dané tvrdenie je už jednoduché. Stačí sa pozrieť na exponenty $a_i(2^t)$, ktoré vieme dostať ako $\log_2 a_i(2^t)$. Napríklad možno ukázať: $$\log_2 a_i(2^t) \equiv \log_2 a_i(2^{t’})+2^{x-1} \pmod {2^x} \implies \log_2 a_{i+1}(2^t) \equiv \log_2 a_{i+1}(2^{t’})+2^{x-2} \pmod{2^{x-1}}.$$ Viacnásobným aplikovaním dostaneme $$\log_2 a_1(2^t) \equiv \log_2 a_1(2^{t’})+2^{m-1} \pmod {2^m} \implies \log_2 a_m(2^t) \equiv \log_2 a_m(2^{t’})+1 \pmod 2,$$ teda ozaj práve jedno z čísel $a_m(2^t)$ a $a_m(2^{t’}+1)$ je štvorec.

1. Ak ste o matematickej indukcii ešte nepočuli, pozrite si to tu↩