10. Koniec Mišovho Šušlania vzorové riešenie



Môžeme si všimnúť, že nakoľko každé prirodzené číslo \(n\) (okrem \(1\)) má aspoň jedného deliteľa menšieho ako \(n\), nahradením \(n\) na okne za jeho delitele počet čísel na okne nikdy nezmenšíme. Zmazaním \(1\) na okne by sme o jedno číslo prišli, preto sa to pri hľadaní maximálneho počtu neoplatí. Taktiež si môžeme premyslieť, že nám nezáleží na poradí, v ktorom čísla na okne mažeme. Keďže na okne sa čísla môžu opakovať, mazanie a dopisovanie deliteľov dvoch čísel sa nijak neovplyvňuje. Ako stratégiu pri hľadaní maximálneho počtu čísel na okne pre určité začiatočné \(n\) si môžeme teda určiť to, že pokiaľ číslo na okne nie je \(1\), zmažeme ho a napíšeme na okno jeho delitele. Tento krok budeme opakovať, až pokým na okne nezostanú iba jednotky.

Označme \(f(n)\) maximálny počet čísel na okne, ktorý môžeme dostať, ak začíname s číslom \(n\). Zo stratégie, ktorú sme vytvorili, si môžeme odvodiť rekurzívny vzorec \[f(n) = \sum_{d\in D} f(d), \qquad (1)\] kde \(D\) je množina deliteľov čísla \(n\), ktoré sú menšie ako \(n\). Naším cieľom je nájsť všetky čísla, pre ktoré platí \(f(n) \geq n\).

Ak je na okne číslo \(1\), hneď na začiatku máme na okne \(1^2\) čísel. Zmazaním jednotky by sme na okne nedostali žiadne číslo, a zároveň by sme nemohli spraviť žiadny ďalší krok. Je teda zjavné, že \(f(1)=1\). Dostávame, že pre \(n=1\) platí \(f(n) \geq n\).

Poďme dokázať, že žiadne iné také \(n\) neexistuje, resp. že \(f(n) < n^2\) pre všetky \(n > 1\). Využijeme na to silnú matematickú indukciu ¹. Ako základ použijeme, že ak je na okne prvočíslo \(p\), vieme ho nahradiť iba číslom \(1\), pre ktoré už vieme, že \(f(1)=1\). Z toho si vieme odvodiť aj hodnotu pre \(f(p) = 1 \leq p^2\). Indukčným predpokladom bude, že \(f(k) \leq k^2\) platí pre všetky čísla \(k\) také, že \(1 < k < n\). Chceme dokázať, že \(f(n) < n^2\).

Na okne majme zložené číslo \(n\). Aby sme sa niekam pohli, musíme nahradiť práve toto číslo jeho deliteľmi (okrem \(n\)). Označme množinu deliteľov čísla \(n\) ako \(D := \{d_1, d_2, \dots, d_i\}\). Keďže \(n\) je zložené, vieme povedať, že má aspoň \(3\) delitele, teda \(i \geq 3\). Všetky tieto delitele však vieme zapísať aj ako \[d_j = \frac{n}{d_{i-j+1}},\qquad 1 \leq j \leq i.\] Množina \(D\) sa týmto zápisom nezmení, a teda \[D = \bigg\{\frac{n}{d_1}, \frac{n}{d_2}, \dots, \frac{n}{d_i}\bigg\}.\] Pre nás sú však zaujímavé len delitele menšie ako \(n\). Bez ujmy na všeobecnosti môžeme povedať, že \(d_i = 1\). Množinu deliteľov menších ako \(n\) si označme \(D'\): \[D' = \bigg\{\frac{n}{d_1}, \frac{n}{d_2}, \dots, \frac{n}{d_{i-1}}\bigg\}.\] Pre deliteľ \(1\) vieme povedať, že \(f(1) = 1\). Voľba \(d_i = 1\) nám určuje \(d_1 = n\), teda \(n/d_1 = 1\) a \(f(n/d_1) = 1\). Keďže všetky ostatné delitele sú väčšie ako \(1\) a menšie ako \(n\), z indukčného predpokladu pre ne platí \[f\:\left(\frac{n}{d_j}\right) < \frac{n^2}{d_j^2},\qquad 2 \leq j \leq i-1.\] Sčítaním týchto nerovností pre všetky \(j\) dostávame \[\sum_{j=2}^{i-1} f\:\left(\frac{n}{d_j}\right) < \sum_{j=2}^{i-1} \frac{n^2}{d_j^2}.\] Treba podotknúť, že keďže \(i \geq 3\), bude mať táto suma vždy aspoň jeden člen. Použitím rekurzívneho vzorca \((1)\), hodnoty \(f(n/d_1) = 1\) a predošlej sumy vieme vyjadriť horný odhad pre \(f(n)\): \[f(n) = \sum_{j=1}^{i-1} f\:\left(\frac{n}{d_j}\right) = 1 + \sum_{j=2}^{i-1} f\:\left(\frac{n}{d_j}\right) < 1 + \sum_{j=2}^{i-1} \frac{n^2}{d_j^2} = 1 + n^2\sum_{j=2}^{i-1} \frac{1}{d_j^2} = n^2\left(\frac{1}{n^2} + \sum_{j=2}^{i-1} \frac{1}{d_j^2}\right). \qquad (2)\] V tomto bode nám už stačí dokázať, že \[\frac{1}{n^2} + \sum_{j=2}^{i-1} \frac{1}{d_j^2} \leq 1. \qquad (3)\] Je známe², že \[\sum_{m=1}^{\infty} \frac{1}{m^2} = \frac{\pi^2}{6}.\] Aby bola táto nekonečná suma pre nás užitočná, odčítajme od oboch strán \(1\): \[\sum_{m=2}^{\infty} \frac{1}{m^2} = \frac{\pi^2}{6} - 1.\] Keď si porovnáme túto sumu so sumou v našej nerovnosti \((3)\), môžeme si všimnúť, že ľavá strana nerovnosti pozostáva z konečne veľa členov tejto sumy (a žiadny člen sa neopakuje). Ďalej si môžeme všimnúť, že pri žiadnych z týchto členov nie je menovateľ v zlomku rovný \(1\) (to vysvetľuje, prečo sme v predošlom kroku odčítali \(1\)). Vieme teda povedať, že \[\frac{1}{n^2} + \sum_{j=2}^{i-1} \frac{1}{d_j^2} < \sum_{m=2}^{\infty} \frac{1}{m^2} = \frac{\pi^2}{6} - 1 < 1,\] čo je to, čo sme potrebovali dokázať. Dosadením tejto hodnoty naspäť do \((2)\) dostávame \(f(n) < n^2\) pre \(n > 1\), čím je dôkaz ukončený. Jediným číslom, pre ktoré vie Mišo po nejakom počte krokov dostať na okne aspoň \(n^2\) (nie nutne rôznych) čísel, je \(1\).