Zadanie
Každý dobrý otvárací ceremoniál sa končí veľkou hostinou. V Blagorade sa vždy na hostinách podávajú koláče. David si všimol, že počty koláčov na jednotlivých podnosoch spĺňajú zaujímavé vlastnosti.
Zvoľme si kladné celé číslo \(n\). Cifru \(c\) nazveme končiteľom čísla \(n\), ak existuje deliteľ čísla \(n\), ktorého posledná cifra je \(c\). Napríklad číslo \(156\) má končitele \(1,\ 2,\ 3,\ 4,\ 6,\ 8\ \text{a}\ 9\).
Nájdite najmenšie zložené číslo, ktoré má práve jeden končiteľ.
Ukážte, že číslo, ktoré má končitele \(0\) a \(9\), musí mať aspoň štyri ďalšie rôzne končitele.
Nájdite najmenšie číslo, ktoré má práve \(10\) končiteľov.
Najskôr si musíme uvedomiť, že každé číslo je deliteľné číslom 1. Preto, ak má mať nejaké číslo práve jeden končiteľ, musí ním byť 1. Aby bolo číslo zložené, musí byť násobkom aspoň dvoch čísel, ktoré sú rôzne od 1. Aby sme nezískali končitele rôzne od 1, tak musí byť naše hľadané číslo násobkom iba čísel končiacich cifrou 1. Najmenšie číslo, ktoré končí cifrou 1 a je rôzne od 1, je 11. To je ale prvočíslo. Preto najmenšie zložené číslo, ktoré má práve jeden končiteľ, je číslo \(11 \cdot 11 = 121\).
Ak má číslo končiteľ 0, tak musí byť deliteľné číslom 10, a teda aj číslami 2 a 5, čo vyplýva z pravidiel deliteľnosti pre 2 a 5. Ak je teda číslo deliteľné dvomi a nejakým číslom, ktoré končí cifrou 9, tak bude deliteľné aj ich spoločným násobkom, ktorý bude končiť cifrou 8. A ako sme už povedali, 1 je končiteľom každého čísla, preto číslo s končiteľmi 0 a 9 bude mať ešte aspoň končitele 1, 2, 5 a 8.
To, že má číslo práve 10 končiteľov znamená, že má všetky možné končitele od 0 po 9. Aby malo končiteľa 0, musí byť toto číslo deliteľné číslom 10, vďaka čomu bude zároveň deliteľné číslami 2 a 5 (a 1 ako každé číslo). Preto naše hľadané číslo bude mať určite v prvočíselnom rozklade \(2 \cdot 5\). To by sme teda mali vybavené končitele 0, 1, 2 a 5. Keďže má mať aj končiteľ 9, tak podľa predchádzajúcej podúlohy bude mať automaticky aj končiteľ 8, takže ten nepotrebujeme riešiť. Podobne, ak bude mať končitele 2 a 7, tak bude mať aj končiteľ 4, a ak bude mať číslo končitele 2 a 3, tak bude mať aj končiteľ 6, preto nám stačí nájsť najmenšie také číslo, ktoré bude mať ešte končitele 3, 7 a 9. Pri ich získavaní nám nijak nepomôže to, že už máme \(2 \cdot 5\), pretože pri násobení ľubovoľného čísla dvomi získame iba párne končitele a pri násobení ľubovoľného čísla piatimi vieme dostať iba končitele 0 a 5, ktoré už ale máme. Takže pridávať budeme iba nepárnych prvočiniteľov rôznych od 5. Ďalšia vec, ktorá nám pomôže je, že pri násobení dvoch alebo viacerých čísel, posledná cifra súčinu závisí iba od posledných cifier jeho činiteľov. Preto keď sa pozrieme na prvočíselný rozklad hľadaného čísla, určite tam nechceme pridávať čísla, ktoré majú viac cifier, lebo by sa dali nahradiť menšími prvočíslami (prvočísla končiace 3 a 7 vieme priamo nahradiť 3 a 7, prvočísla končiace 9 vieme nahradiť \(3 \cdot 3\), čo dáva menší súčin ako ľubovoľné prvočíslo končiace cifrou 9). Takže z toho vyplýva, že budeme pridávať už len 3 a 7. Pridaním iba jedného ďalšieho prvočiniteľa by sme získali maximálne 2 nové končitele, a to končiteľ pridaného prvočísla a končiteľ jeho dvojnásobku. Takže potrebujeme pridať aspoň 2 prvočinitele. Na to máme možnosti:
\(3 \cdot 3\) - pribudnú nám nepárne končitele 3 a 9, stále nám ale chýba 7
\(3 \cdot 7\) - pribudnú končitele 3 a 7, ale stále chýba 9
\(7 \cdot 7\) - pribudnú končitele 7 a 9, ale stále chýba 3
Preto potrebujeme pridať aspoň 3 prvočinitele. Najmenšia možnosť je pridať \(3 \cdot 3 \cdot 3\), čím získame aj končiteľ 3 (samotná 3), aj končiteľ 9 (\(3 \cdot 3\)), aj končiteľ 7 (\(3 \cdot 3 \cdot 3\)). Ako sme si už skôr povedali, vďaka tomu získame aj všetky chýbajúce párne končitele, teda sme našli najmenšie číslo, ktoré má práve 10 končiteľov, a je ním číslo \(2 \cdot 3 \cdot 3 \cdot 3 \cdot 5 = 270\).
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ť.