8. Kamaráti Miro Slavomír vzorové riešenie

Základná veta v úlohách s \(\operatorname{NSN}\) (najmenší spoločný násobok) a \(\operatorname{NSD}\) (najväčší spoločný deliteľ) ktorá sa využíva je indukcia a identita \[ab=\operatorname{NSD}(a,b)\operatorname{NSN}(a,b).\]

Ukážeme, že výsledok je \(n\), teda že na konci na papieri bude určite aspoň \(n\) rôznych čísel. Ako prvé si ukážeme konštrukciu: Ak sú Slavove obľúbené čísla \(2^0,\ 2^1,\ 2^2,\ \dots,\ 2^{n-1}\), potom na papieri budú napísané práve čísla \(2^0,\ 2^1,\ 2^2,\ \dots,\ 2^{n-1}\) a žiadne iné, pretože \(\operatorname{NSD}\) aj \(\operatorname{NSN}\) mocnín dvojky menších ako \(2^n\) je mocnina dvojky menšia ako \(2^n\), a teda je na tabuli. ¹

Dôkaz, že ich je aspoň \(n\) je o niečo zložitejší – treba si po prvé prečítať správne zadanie a všimnúť si, že Slavove čísla nie sú na začiatku na tabuli napísané a teda nie je zjavné že ich musí byť aspoň \(n\). Ako budeme dokazovať, že to nejde na menej ako \(n\)? Ak v príklade vidíme vetu „dokážte pre prirodzené \(n\), že...“, tak automaticky použijeme indukciu. Pre \(n=2\) to zjavne platí. Predpokladáme, že pre \(k=2, \dots, n-1\) platí, že ak je Slavova množina veľkosti \(k\), potom na konci na papieri bude aspoň \(k\) čísel. Ďalej to dokážeme pre \(k=n\).

Označme si Slavove čísla \(x_1,\ \dots,\ x_n\). O čo sa budeme snažiť – chceme rozdeliť túto množinu čísel na dve menšie množiny, na ktoré budeme môcť použiť indukčný predpoklad a vrámci prvej množiny bude mať každá dvojica rozdielne \(\operatorname{NSD}\) aj \(\operatorname{NSN}\) oproti všetkým \(\operatorname{NSD}\) a \(\operatorname{NSN}\) vrámci druhej množiny.

Vezmime si prvočíslo \(p\), ktoré delí aspoň dve Slavove čísla. Také číslo musí existovať, pretože ak by neexistovalo znamenalo by to že všetky čísla sú nesúdeliteľné a teda čísla \(\operatorname{NSN}(x_1, x_2),\ \operatorname{NSN}(x_1, x_3),\ \dots,\ \operatorname{NSN}(x_1, x_n)\) sú rôzne a spolu s číslom \(1\) bude na papieri aspoň \(n\) čísel. Nech toto prvočíslo \(p\) delí práve \(m\) Slavových čísel, kde určite \(2\leq m\leq n\).

Týmto sa nám všetky Slavove čísla rozdelili na dve množiny – tie, ktoré sú deliteľné prvočíslom \(p\) a na tie, ktoré nie sú deliteľné číslom \(p\). Teraz príde hlavná myšlienka: tieto dve skupiny majú rozdielne všetky \(\operatorname{NSN}\) a \(\operatorname{NSD}\) – ak spravíme \(\operatorname{NSN}\) alebo \(\operatorname{NSD}\) ľubovoľnej dvojice v jednej skupine, tak bude iné ako \(\operatorname{NSN}\) či \(\operatorname{NSD}\) ľubovoľnej dvojice v druhej skupine, pretože v prvej bude \(\operatorname{NSN}\) aj \(\operatorname{NSD}\) deliteľné prvočíslom \(p\) a v druhej nie. Takže použijeme indukčný predpoklad. Prvá skupina na papier aspoň \(m\) čísel a druhá aspoň \(n-m\) čísel. Všetky sú vďaka tejto rozdielnosti \(\operatorname{NSN}\) a \(\operatorname{NSD}\) rôzne, teda ich spolu bude aspoň \(n\). Jediný problém môže nastať, ak jedno z čísel \(m\), \(n-m\) nie je v množine indukčného predpokladu, čo nastane iba ak \(m=n\) alebo \(m=n-1\). Toto sú ale ľahké možnosti. Ak \(m=n\) potom všetky čísla sú deliteľné číslom \(p\). Teda môžeme vyňať \(p\), opakovať celý postup a vyjde nám to isté. Na druhej strane, ak \(m=n-1\), to znamená, že práve jedno číslo (označme si ho \(x_k\)) nie je deliteľné \(p\). Tu ale taktiež môžeme použiť indukčný predpoklad, \(n-1\) čísel bude mať aspoň \(n-1\) rozdielnych \(\operatorname{NSD}, \operatorname{NSN}\) a k nim pridáme \(\operatorname{NSD}(x_k, x_1)\) ktoré ako jediné nie je deliteľné číslom \(p\) a teda so všetkými rozdielne. Teda spolu je na papieri aspoň \(n\) rôznych čísel.