9. Kružilašom Míňame Šamorín vzorové riešenie

Uvažovať zvyšky po delení všetkými číslami \(1\leq k\leq n-1\) je trochu veľa možností čo naraz uvažovať. Preto sa oplatí uvažovať zvyšky po delení takým číslom, aby tých zvyškov bolo málo. Takým deliteľom je napríklad \(k=n-1\). Zvyšok \(1\) po delení \(k=n-1\) nadobúda iba \(1\) a \(n\) a každé ďalšie z čísel \(2,3,\dots n-1\) nadobúda iný zvyšok. Preto je buď \(1\), alebo \(n\) na poslednom mieste, pretože nemôžu byť obe v prvej \((n-1)\)-tici. Počet takých \(n\)-tíc, kde \(n\) je na poslednom mieste, je vlastne úloha pre \(n-1\), a je ich toľko, koľko je takých \((n-1)\)-tíc. A počet možností, kde je \(1\) na konci, je zatiaľ neznámy. Avšak môžeme tušiť, že po delení \(n-2\) budú potom zase práve dve čísla s rovnakým zvyškom a jedno z nich bude musieť byť na predposlednom mieste. Pre predposledné miesto máme teda možnosti \((\dots,2,1),(\dots,n,1),(\dots,1,n),(\dots,n-1,n)\). Tieto pozorovania nám napovedajú, že by sa mohlo jednať o dôkaz indukciou a výsledok by mohol byť \(2^{n-1}\). Poďme to teda dokázať indukciou.

Budeme matematickou indukciou zhora dokazovať tvrdenie, že od konca budeme mať postupnosť čísel, kde každé ďalšie číslo je buď najväčšie nepoužité, alebo najmenšie nepoužité číslo. Pričom na výbere nebude záležať a teda budú vždy dve možnosti na \(k\)-tu pozíciu.

Pre posledné miesto už vieme, že máme dve možnosti \(1\) a \(n\).

Nech od konca máme postupnosť čísel, ktorá spĺňa predpoklad indukcie, kde použijeme čísla \(1,2,\dots, m\) a \(n-s+1,n-s+2,\dots, n\). Potom nepoužité čísla sú \(m+1, m+2, \dots, n-s\) a je ich \(n-m-s\). Tieto čísla sú po sebe idúce čísla, a teda po delení \(n-m-s-1\) majú čísla \(m+1\) a \(n-s\) rovnaké zvyšky. Ostatné čísla musia mať rôzne zvyšky. Preto na \((m+s+1)\)-tom mieste od konca (\((n-m-s)\)-tom mieste) musí byť práve jedno z týchto dvoch čísel. Preto máme dve možnosti na \((m+s+1)\)-té číslo od konca a zároveň sme použili buď najväčšie, alebo najmenšie nepoužité číslo.

Táto indukcia pokračuje, až kým nezostane posledné číslo, a to na prvom mieste, budeme mať iba jednu možnosť. Preto je počet možností Mišov \(2^{n-1}\).

Ešte musíme overiť, že každá takáto postupnosť naozaj spĺňa podmienky zo zadania. Lenže pri konštrukcií sme uvažovali všetky \(k\) od \(n-1\) po \(2\), a teda takto skonštruovaná postupnosť ozaj spĺňa podmienku zo zadania.