Zadanie
Miloš bol veľkým fanúšikom kúziel a vždy hľadal spôsoby, ako sa ich naučiť viac. Kedysi dávno počul o veľmi silnom kúzle, v ktorom sa vyskytovali čísla, ktoré ale dlho nevedel nájsť.
Kúzelník Miloš bol šťastný, pretože po dlhých rokoch hľadania konečne našiel všetky prirodzené čísla \(N\), ktoré sa v desiatkovej sústave skladajú presne z \(1112\) cifier a spĺňajú všetky tieto podmienky:
súčet všetkých cifier čísla \(N\) je deliteľný \(2000\);
súčet všetkých cifier čísla \(N + 1\) je tiež deliteľný \(2000\);
číslo \(N\) obsahuje cifru \(1\).
Určte všetky čísla, ktoré kúzelník Miloš našiel.
Začnime tým, že sa pozrieme na to, ako sa zmení ciferný súčet, keď k číslu pripočítame \(1\). Najjednoduchší prípad nastane, keď číslo končilo niektorou z cifier od \(0\) po \(8\). Táto cifra sa zvýši o jedna a ostatné cifry zostanú nezmenené. Nový ciferný súčet teda bude o \(1\) väčší.
Predstavme si, že na konci čísla je cifra \(9\). Pripočítaním jednotky sa posledná cifra zmení na \(0\) a k predošlej cifre budeme musieť pripočítať \(1\) – „prechod cez desiatku“. Ak však pred našou deviatkou bola ďalšia deviatka, proces sa zopakuje. Aj predposledná cifra sa zmení na \(0\) a k cifre pred ňou sa opäť pripočíta \(1\). Takto to pôjde ďalej až nenarazíme na cifru rôznu od \(9\), alebo sa nám neminú cifry. V druhom prípade jednoducho pred číslo dopíšeme jednotku.
Označme \(m\) počet deviatok na konci hľadaného čísla \(N\). Určite platí \(0 \leq m \leq 1112\). Ako sme si všimli vyššie, číslo \(N + 1\) dostaneme tak, že každú z \(m\) deviatok na konci nahradíme \(0\) a cifru pred deviatkami zvýšime o \(1\). (Alebo pridáme \(1\) na začiatok ak \(m = 1112\).) Ciferný súčet sa zníži o \(9 \cdot m\) za zmenené deviatky a zvýši o \(1\) za zmenu (resp. pridanie) cifry pred deviatkami.
Vráťme sa k podmienkam zo zadania. Označme \(c\) ciferný súčet čísla \(N\). Ciferný súčet čísla \(N+1\) bude, podľa postupu vyššie, rovný \(c + 1 - 9m\). Podľa zadania majú byť obe tieto hodnoty násobkami \(2000\). Potom ale aj rozdiel týchto dvoch hodnôt, t. j. \(9m - 1\), musí byť násobkom \(2000\). To nám samo o sebe nič nezaručí, ale obmedzí nám to možné hodnoty \(m\). Keďže \(m \leq 1112\), nutne \(9m - 1 \leq 10~007\). Správny násobok \(2000\) je teda jeden z \(0,\, 2000,\, 4000,\, 8000,\, 10~000\). Vieme tiež, že \(9m\) je násobok \(9\), čo platí len pre hodnotu \(8001\), takže vyhovujúci násobok je \(8000\) a jediné vyhovujúce \(m\) bude \(889\).
Prišli sme na to, že \(N\) má na konci \(889\) deviatok (a že pred nimi je iná cifra ako \(9\)). Vieme tiež, že \(N+1\) má ciferný súčet o \(8000\) menší. Keďže \(N+1\) má mať ciferný súčet, ktorý je násobkom \(2000\), musí to byť najmenej \(2000\). Ciferný súčet \(N\) bude teda aspoň \(10~000\). Aký najväčší ciferný súčet môže číslo \(N\) mať? Najviac to bude \(10~008 = 1112 \cdot 9\), čo je prípad, kedy každá cifra \(N\) je deviatka. Jediný vyhovujúci ciferný súčet pre \(N\) je teda práve spomínaných \(10~000\).
Ako teda môže číslo \(N\) vyzerať? Na konci má \(889\) deviatok, pred ktorými je cifra menšia ako \(9\). Ak by to bola cifra \(8\) a všetky ostatné cifry by boli \(9\) ciferný súčet by bol \(10~007\), nie \(10~000\). Cifry takéhoto čísla nemôžeme zvyšovať, len znižovať. Tiež musíme pamätať na poslednú podmienku zo zadania – číslo \(N\) obsahuje cifru \(1\). Ak by sme niektorú z deviatok v našom čísle nahradili \(1\) dostali by sme číslo s ciferným súčtom menším ako \(10~000\). Jediná cifra, ktorú vieme nahradiť jednotkou, je teda jediná rôzna od \(9\), a to je \(8\) na \(890.\) mieste sprava.
Takže jediné možné \(N\) začína \(1112 - 889 - 1 = 222\) deviatkami, potom nasleduje \(1\) jednotka a nakoniec \(889\) deviatok. Mali by sme ešte overiť, že toto číslo skutočne spĺňa všetky tri podmienky zo zadania. Jeho ciferný súčet je \(1111 \cdot 9 + 1 = 10~000\). \(N+1\) má ciferný súčet \(222 \cdot 9 + 2 = 2000\). Jednotku naše \(N\) má, takže je skutočne riešením.
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ť.