9. Krútia Makovice Sa vzorové riešenie

Našou úlohou je nájsť všetky čísla \(A\), ktoré delia všetky svoje cyklické rotácie cifier (jednotlivé \(A_k\)). Predpokladajme, že máme nejaké také číslo \(A\). Toto číslo musí deliť aj číslo, ktoré dostaneme tak, že jeho prvú cifru presunieme na koniec (\(A_1\)). Poďme si toto číslo vyjadriť. Od \(A\) musíme odpočítať \((10^{n-1})\)-násobok prvej cifry, vynásobiť ho desiatimi (čo posunie všetky cifry) a cifru, ktorá bola pôvodne prvá, pripočítať: \[A \mid (A-10^{n-1}a_{n-1})\cdot 10 + a_{n-1}.\]

Deliteľnosť znamená, že pravá strana je \(k\)-násobkom ľavej strany pre nejaké celé číslo \(k\) (nesúvisí s \(k\), ktorými zadanie indexuje \(A_k\)): \[\begin{align} kA &= (A-10^{n-1}a_{n-1})\cdot 10 + a_{n-1},\\ kA &= 10A - 10^n a_{n-1} + a_{n-1},\\ (10-k)A &= a_{n-1}(10^n-1).\end{align}\]

Pravá strana je zrejme kladná, takže aj ľavá musí byť. Aj číslo \(k\) musí byť kladné a musí preto platiť \(1 \leq k \leq 9\), čiže aj \(1 \leq 10 - k \leq 9\). Pozrime sa teraz na všetky možné hodnoty činiteľa \((10 - k)\) na ľavej strane rovnosti: \[\begin{align} 10-k &= 1 & A &= \frac{a_{n-1} \cdot (10^n-1)}{1} = a_{n-1} \cdot 999\dots9 \\ 10-k &= 2 & A &= \frac{a_{n-1} \cdot (10^n-1)}{2} = \frac{a_{n-1}}{2} \cdot 999\dots9 \\ 10-k &= 3 & A &= \frac{a_{n-1} \cdot (10^n-1)}{3} = a_{n-1} \cdot 333\dots3 \\ 10-k &= 4 & A &= \frac{a_{n-1} \cdot (10^n-1)}{4} = \frac{a_{n-1}}{4} \cdot 999\dots9 \\ 10-k &= 5 & A &= \frac{a_{n-1} \cdot (10^n-1)}{5} =\frac{a_{n-1}}{5} \cdot 999\dots9 \\ 10-k &= 6 & A &= \frac{a_{n-1} \cdot (10^n-1)}{6} = \frac{a_{n-1}}{2} \cdot 333\dots3 \\ 10-k &= 7 & &\textrm{necháme si na neskôr} \\ 10-k &= 8 & A &= \frac{a_{n-1} \cdot (10^n-1)}{8} = \frac{a_{n-1}}{8} \cdot 999\dots9 \\ 10-k &= 9 & A &= \frac{a_{n-1} \cdot (10^n-1)}{9} = a_{n-1} \cdot 111\dots1\end{align}\]

Z týchto prípadov okrem \(10 - k = 7\) nevieme získať žiadne riešenie našej úlohy, pretože \(A\) musí byť násobkom čísla so samými rovnakými ciframi, ale taký násobok bude tiež mať všetky cifry rovnaké, čo nám nevyhovuje, alebo bude mať cifier viac, ale číslo \(A\) musí mať presne toľko cifier, koľko je devín, trojok či jednotiek (ich počet je \(n\)). Všetky zlomky v tabuľke typu \(\frac{a_{n-1}}{i}\) sú pritom naozaj celé čísla, pretože príslušné \(i\) sú s číslami so samými rovnakými ciframi v tom istom riadku nesúdeliteľné.

Preskúmajme napokon jediný ostávajúci prípad \(10 - k = 7\). Má platiť \[7A = a_{n-1}(10^n-1).\] Ľavá strana je násobkom \(7\), teda aj pravá musí byť. Ak by \(a_{n-1} = 7\) (je to len jedna cifra), tak by sme mali \(A = (10^n-1) = 999\dots9\), čo nám nevyhovuje. Preto musí byť siedmimi deliteľné \(10^n-1\). Keď si vypíšeme zvyšky \(10^n\) po delení \(7\), dostaneme \(1, 3, 2, 6, 4, 5, 1, 3, \dots\) a ďalej sa budú cyklicky opakovať, pretože každý zvyšok je jednoznačne určený predošlým. Musí teda platiť \(n = 6m\). V tom prípade máme \[\begin{align} 7A &= a_{n-1}(10^n-1), \\ A &= a_{n-1} \cdot 142857142857\dots142857.\end{align}\]

Máme číslo, v ktorom sa opakuje perióda cifier \(142857\). Násobky takého čísla vyzerajú tak, že sa opakuje jedna z periód \(142857, 285714, 428571, 571428, 714285, 857142\) (ďalším je už \(999999\)). Ak by sme za \(a_{n-1}\) vzali čokoľvek väčšie ako \(1\), číslo \(A\) by obsahovalo cifru \(1\), ale by ňou nezačínalo. Teda cyklická rotácia s jednotkou na začiatku by bola menšia ako \(A\), takže by ju \(A\) nedelilo. Musí totiž stále platiť, že \(A\) má \(n\) cifier, takže \(a_{n-1} > 7\) nepripadá do úvahy.

Máme teda \[A = \frac{10^{6m}-1}{7} = 142857142857\dots142857,\] kde postupnosť \(142857\) sa opakuje \(m\) krát, \(m \in \mathbb{N}\).

Všetky takéto čísla sú riešením našej úlohy, pretože cyklické posuny \(142857\) sú práve uvedené násobky (\(142857\), \(285714\), \(428571\), \(571428\), \(714285\), \(857142\)) a pre čísla s \(m\) opakovaniami tejto periódy to platí tiež, pretože cyklické posúvanie cifier v celom dlhšom čísle je to isté, ako cyklické posúvanie jeho cifier v rámci jednotlivých šestíc. Ak napríklad číslo \(X\) vzniklo cyklickým posunom \(142857\), potom číslo \(\overline{XXXXX}\) vzniklo cyklickým posunom celého zväzku päť po sebe idúcich čísel \(142857\). Z toho aj vyplýva, že cyklické posuny týchto dlhších sekvencií sú násobkami pôvodnej sekvencie, nakoľko jednotlivé šestice cifier sú na sebe nezávislé – nedochádza k žiadnym prenosom/zvyškom medzi nimi. Inak povedané, keď máme \(a \cdot 142857 = X\), tak \(a \cdot 142857142857\dots 142857 = \overline{XX\dots X}\), kde \(X\) je príslušná postupnosť \(6\) cifier.