9. Káčka Množiny S vzorové riešenie

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¹. 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.