Zadanie
Korunováciu vezíra zakončili slávnostné zvolania:
„Nech žije kráľ In Te! Kráľ In Te! Kráľ In Te!“
Nový vládca Al-Gebry sa chystal na príhovor, keď do siene vpadli vyšetrovatelia, aby oznámili novinky. Počúvali ich všetci dvorania aj zástupcovia okolitých krajín. Hlavný vyšetrovateľ povedal:
„Po dosadení všetkých neznámych sme došli k záveru, že vlajka Kombistanu, na ktorej bol kráľ Kardáno Abel Gauss Horner napichnutý, značí jediné. Vraždu si objednal práve Kombistan.“
Všetci boli zhrození, len In Te zachoval chladnú hlavu. Zavolal si zástupcov Teórie Čísel a Matematickej Ľudovo-demokratickej Analýzy a požiadal ich krajiny o pomoc pri odvete za tento hrozný čin. Delegát Teórie Čísel okamžite bežal k telefónu, aby získal informácie z domova.
„Haló, existujú ešte nejaké jednotky, ktoré by sme mohli vyslať na pomoc našim hrdinom z Al-Gebry?“
„Čakajte na linke, čoskoro to zistíme.“
Nájdite všetky kladné celé čísla \(n\), pre ktoré existuje \(n\) navzájom rôznych prirodzených čísel takých, že najväčší spoločný deliteľ každých dvoch z nich je rovný absolútnej hodnote ich rozdielu.
Pre malé \(n\) nie je problém nájsť vhodných \(n\) čísel – keď máme jedno číslo, nemusíme splniť žiadnu podmienku, dve čísla vieme mať napríklad \(6\) a \(8\) s rozdielom aj najväčším spoločným deliteľom (NSD) rovným \(2\).
Úlohu by sme mohli skúsiť vyriešiť postupným pridávaním čísel. Formalizovali by sme to ako matematickú indukciu – ak máme vhodných \(n\) čísel (kde NSD ľubovoľných dvoch z nich je rovný ich rozdielu), pridaním ďalšieho čísla k nim (a prípadnou zmenou ostatných) zostrojíme \((n+1)\)-ticu vyhovujúcich čísel. Keď ukážeme tento krok, vďaka indukcii budeme mať úlohu hotovú, pretože tento krok môžeme opakovať, koľkokrát bude treba.
Ako by sme mohli z \(n\)-tice čísel spĺňajúcej zadanie vytvoriť \((n+1)\)-ticu? Existuje nejaké číslo, ktoré k nej môžeme iba pridať? Áno, vieme pridať číslo \(0\), pretože rozdiel \(0\) a ľubovoľného čísla \(a\) je \(a\), rovnako ako aj ich NSD je \(a\), pretože všetko delí nulu. Toto má ale dva problémy:
\(0\) nie je prirodzené číslo.
Ak už raz pridáme nulu, nemôžeme ju v ďalšom kroku pridať znova (čísla majú byť rôzne).
Oba tieto problémy by sme mohli vyriešiť tým, že všetky čísla zvýšime o pevnú konštantu. Rozdiely sa tým zachovajú, ostáva zvoliť konštantu tak, aby sa zachovali aj NSD dvojíc čísel. Vhodnou konštantou je ľubovoľný spoločný násobok všetkých našich čísel (napr. ich najmenší spoločný násobok alebo ich súčin).
Ak totiž máme čísla \(a, b\) (spomedzi našich \(n\) čísel) a číslo \(c\), ktoré je násobkom každého z nich, tak ak \(d = |a-b| = \operatorname{NSD}(a, b)\), tak nutne platí aj \(d \mid a \mid c\), z čoho \(d\mid a+c\), \(d\mid b+c\), čiže \(d\) je spoločným deliteľom posunutých čísel. Zároveň čísla \(a+c\) a \(b+c\) nemôžu mať spoločného deliteľa väčšieho ako ich rozdiel, čo je \(d\), takže \(d\) je ich najväčší spoločný deliteľ.
Náš indukčný krok teda bude vyzerať tak, že vezmeme \(n\) čísel spĺňajúcich zadanie, pridáme k nim nulu (nie je ešte medzi nimi, lebo tie čísla sú prirodzené) a zvýšime všetky o ich spoločný násobok (ak použijeme súčin, tak do násobenia tú nulu, samozrejme, nezahrnieme), čím dostaneme \(n+1\) prirodzených čísel (aj najmenšia nula sa zväčšila aspoň o \(1\)).
Dokázali sme, že \(n\) čísel vyhovujúcich danej podmienke vieme nájsť pre ľubovoľné prirodzené číslo \(n\).
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.