3. Kráti Marek Symboly vzorové riešenie

Aby sme nemuseli stále vypisovať, že nejaké číslo sa dá zredukovať na číslo \(1\), budeme takéto číslo skrátene volať . Teda našou úlohou je nájsť všetky zredukovateľné čísla.

Jednociferné čísla sú zredukovateľné, pretože číslo po predelení samým sebou je \(1\). Ak vieme číslo zredukovať na jednociferné číslo, tak ho následne vieme zredukovať aj na jednotku.

Ak číslo má poslednú cifru \(1\), tak redukovaním dostávame to isté číslo. Teda jediné zredukovateľné číslo s poslednou cifrou \(1\) je práve číslo \(1\). Neexistuje prirodzené číslo deliteľné nulou, preto čísla s poslednou cifrou \(0\) nevieme redukovať. Ostávajú nám tak čísla, ktoré majú aspoň dve cifry a nekončia sa cifrou \(0\) ani \(1\).

Pozrime sa najprv, čo sa deje pri redukovaní. Zoberme si číslo \(x\) s poslednou cifrou \(a\). Označme si číslo, ktoré vznikne po zredukovaní \(x\) ako \(y\). Teda \(y = x/a\) alebo po prenásobení \(a \cdot y = x\). Aby táto rovnosť platila, musí mať súčin \(a \cdot y\) poslednú cifru rovnú \(a\). Označme si poslednú cifru čísla \(y\) ako \(b\). Zjavne čísla \(a \cdot y\) a \(a \cdot b\) majú rovnakú poslednú cifru.

Nájdime teraz všetky dvojice cifier \((a,b)\), pre ktoré má súčin \(a \cdot b\) poslednú cifru \(a\) a obe cifry sú rôzne od nuly a jednotky. Napríklad to môžeme spraviť tak, že najprv pre \(a=2\) nájdeme všetky vyhovujúce cifry \(b\), potom pre \(a=3\) atď. Nájdeme tak nasledovné dvojice \((a,b)\) (vždy na prvom mieste je \(a\) a na druhom \(b\)): \[(2,6),\, (4,6),\, (6,6),\, (8,6),\, (5,3),\, (5,5),\, (5,7),\, (5,9).\] Poďme teraz rozobrať jednotlivé možnosti.

Začneme najprv s jednoduchším prípadom. Zoberieme si aspoň dvojciferné číslo \(x\) s poslednou cifrou \(a=6\), ktoré je zredukovateľné. Jediná dvojica \((a,b)\), kde \(a=6\), je dvojica \((6,6)\). Preto redukovaním takéhoto čísla \(x\) získame číslo končiace cifrou \(6\), ktoré je tiež zredukovateľné. Ak budeme redukcie opakovať, tak stále budeme dostávať zredukovateľné čísla končiace šestkou. Nakoniec dostaneme jednociferné číslo \(6\), ktoré zredukujeme na \(1\). Ak sa na tento proces pozrieme od konca, tak číslo \(1\) sme násobili niekoľko krát šiestimi. Preto všetky zredukovateľné čísla, ktoré majú poslednú cifru \(6\), sú tvaru \(6^k\) pre nejaké kladné celé číslo \(k\) (zahrnuli sme sem už aj jednociferné číslo \(6\)).

Ďalej si zoberme zredukovateľné číslo \(x \ge 10\) s poslednou cifrou \(a=2\). Opäť z nášho zoznamu dvojíc vidíme, že jediné vyhovujúce \(b\) je \(b=6\). Preto redukovaním čísla \(x\) dostaneme zredukovateľné číslo \(y\) končiace cifrou \(6\). Tieto čísla sme už však našli, preto \(y=6^k\) pre nejaké celé kladné číslo \(k\). Číslo \(x\) získame z čísla \(y\) vynásobením \(a=2\), a teda \(x\) musí byť v tomto prípade tvaru \(2 \cdot 6^k\). Rovnakým spôsobom zistíme, že jediné zredukovateľné čísla končiace cifrou \(4\), resp. \(8\) sú čísla tvaru \(4 \cdot 6^k\), resp. \(8 \cdot 6^k\).

V našom zozname dvojíc \((a,b)\) sa nenachádza dvojica, kde by \(a\) bolo nejaké z čísel \(3\), \(7\) alebo \(9\). Preto neexistuje žiadne zredukovateľné číslo, ktoré má aspoň dve cifry a končí cifrou \(3\), \(7\) alebo \(9\).

Ostáva nám teda posledný prípad, a to prípad, kedy zredukovateľné číslo \(x \ge 10\) končí na cifru \(a=5\). Z nášho zoznamu vidíme, že po zredukovaní čísla \(x\) dostaneme číslo končiace cifrou \(3\), \(5\), \(7\) alebo \(9\). Avšak už vieme, že jediné zredukovateľné čísla končiace na \(3\), \(7\) alebo \(9\) sú \(3\), \(7\) a \(9\). V taktom to prípade naše redukovanie končí. Ak po redukcii čísla \(x\) dostaneme číslo končiace cifrou \(5\), sme v rovnakej situácii, ako na začiatku. Teda v tomto prípade vyzerá redukovanie tak, že ich najprv delíme piatimi, kým to ide. Nakoniec sa dopracujeme buď k číslu \(5\) a následne \(1\), alebo k číslu \(3\), \(7\) alebo \(9\), z ktorého jednou redukciou dostaneme číslo \(1\). Ak sa ne tento proces pozrieme spätne, tak najprv jednotku vynásobíme číslom \(3\), \(5\), \(7\) alebo \(9\) a potom ho len násobíme piatimi. Teda získavame tak zredukovateľné čísla tvarov \(3\cdot 5^k\), \(5^k\), \(7 \cdot 5^k\) a \(9\cdot 5^k\) pre nejaké kladné celé číslo \(k\).

Jendociferné čísla sme vyriešili zvlášť a pri viacciferných číslach sme rozobrali všetky možnosti poslednej cifry. Všetky zredukovateľné čísla teda sú čísla tvarov \(2\cdot 6^k\), \(3\cdot 5^k\), \(4\cdot 6^k\), \(5^k\), \(6^k\), \(7\cdot 5^k\), \(8\cdot 6^k\), \(9\cdot 5^k\), kde \(k\) je nezáporné celé číslo. Všimnite si, že tento zápis zahŕňa aj všetky jednociferné čísla, stačí si zvoliť \(k=0\), resp. \(k=1\). Zo spôsobu, akým sme ich našli, vyplýva, že všetky tieto čísla naozaj vieme zredukovať na číslo \(1\).