Riešky tábor 2026 - Milí Rieškari, aj toto leto nás čaká Letný tábor Riešok, na ktorý vás srdečne pozývame. Tábor je desaťdňová akcia počas ktorej sa zabavíte, niečo naučíte a hlavne si vytvoríte kopu … Prejsť na článok
×9. príklad - Vzorové riešenie
Zadanie
Ochranku tvorí n (prirodzené číslo) strážcov. Strážcovia sa vedia rôznymi spôsobmi rozdeliť na niekoľko rovnako veľkých skupín, pričom v každej skupine je celočíselný počet strážcov. Ak si zoradíme všetky možné veľkosti týchto skupín od najmenšej po najväčšiu zistíme, že celkový počet strážcov n sa rovná súčtu strážcov trinástej najmenšej skupiny (d13), šestnástej najmenšej skupiny (d16) a sedemnástej najmenšej skupiny (d17). Koľko strážcov môže pracovať v múzeu? Nájdite všetky možnosti.
Vzorové riešenie
Hľadáme všetky n, ktoré sú súčtom svojho 13., 16. a 17. najmenšieho deliteľa. Označíme si všetkých deliteľov n vzostupne 1=d_1 \lt d_2 \lt \dots \lt d_k. Takže hľadáme všetky n, pre ktoré platí n = d_{13} + d_{16} + d_{17}. Uvedomme si, že každý deliteľ n je tvaru \frac{n}{a} pre nejaké kladné celé a.
Platí, že d_{17} \gt \frac{n}{3}, keďže n = d_{13} + d_{16} + d_{17} \lt 3 d_{17}. Taktiež zrejme d_{17} \lt n. Teda nám už len ostáva jediná možnosť a to d_{17} = \frac{n}{2}.
Teraz dostávame d_{13} + d_{16} = \frac{n}{2}. Podobne ako predtým dostávame d_{16} \gt \frac{n}{4}, keďže 2d_{16} \gt d_{13} + d_{16} = \frac{n}{2}. Taktiež \frac{n}{2} = d_{17} \gt d_{16}. Teda nám ostáva len jediná možnosť a to d_{16} = \frac{n}{3}.
Nakoniec máme d_{13} + \frac{n}{3} + \frac{n}{2} = n, z čoho d_{13} = \frac{n}{6}. Medzi d_{13} = \frac{n}{6} a d_{16} = \frac{n}{3} sú 2 deliteľe n. Avšak jediné deliteľe n medzi \frac{n}{3} a \frac{n}{6} môžu byť len \frac{n}{4} a \frac{n}{5}, teda to už nutne musia byť d_{14} a d_{15}.
Všimnime si, že ak d delí n, potom \frac{n}{d} je celé a dokonca delí n, keďže n = d \frac{n}{d}. Vieme, že \frac{n}{2}, \frac{n}{3} a \frac{n}{5} delia n, teda 2, 3 a 5 delia n. Ďalej si uvedomme, že jediné číslo väčšie ako \frac{n}{2}, ktoré delí n je n samotné. A keďže d_{17} = \frac{n}{2}, tak n má práve 18 deliteľov.
Pozrime sa teraz vzhľadom na prvočíselný rozklad čísla m, koľko deliteľov má m. Nech m = p_1^{a_1} \cdot p_2^{a_2} \cdot \dots \cdot p_l^{a_l}. Každý jeho deliteľ má exponent prvočísla p_1 v mocnine 0, 1, \dots, a_1 - 1 alebo a_1, čo je celkovo a_1 + 1 možností. Podobne na exponent prvočísla p_2 máme a_2 + 1 možností, a tak ďalej. Žiadne prvočíslo okrem p_1, p_2, \dots, p_l nemôže deliť deliteľa m. To znamená, že na deliteľa m máme celkovo (a_1 + 1)(a_2 +1) \dots (a_l + 1) možností. Môžeme si všimnúť, že počet deliteľov je deliteľný aspoň toľkými prvočíslami, koľkými rôznymi prvočíslami je deliteľné m, keďže každý rôzny prvočíselný deliteľ m prispieva jednou zátvorkou a každá zátvorka prispieva aspoň jedným prvočíselným deliteľom.
Teraz však ale máme, že n je deliteľné 2, 3, 5 a má 18 = 2 \cdot 3\cdot 3 deliteľov. n už nemôže byť deliteľné ďalším rôznym prvočíselným deliteľom, keďže by n bolo deliteľné viacerými rôznymi prvočíslami ako má 18 celkovo prvočíselných deliteľov a to sa nemôže stať. Takže n = 2^{a_1} \cdot 3^{a_2} \cdot 5^{a_3}, pričom vieme, že a_1 +1, a_2 +1, a_3+1 tvoria 2, 3, 3 v nejakom poradí, teda máme 3 rôzne možnosti a_1 = 1, a_2 = a_3 = 2 alebo a_2 = 1, a_1 = a_3 = 2 alebo a_3 = 1, a_1 = a_2 = 2. Dosadením môžeme ľahko overiť, že vychádzajú iba druhé dve možnosti, pre ktoré n = 300 a n = 180.