Opravovatelia

Michal S. [email protected]

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.