Zadanie
Nad mestom sa vznášal prach. A predsa bolo vidieť šerifskú hviezdu nad vchodom do úradu Sgt. Peppera. Ak niekto americké Marlborough držal na krátko a prinášal do všedných dní vraždenia, krvi a krčmových duelov poriadok, tak to bol on. Muž činu a legenda, Sheriff Sgt. Pepper. Ale zase nepreháňajme. Nie každý deň bolo treba volať hrobára. Napríklad dnes jediným problémom, ktorý Sgt. Pepper riešil, bolo hľadanie strateného dobytka1 statkára Ritza:
Nájdite všetky prirodzené čísla \(n\), pre ktoré existuje \(n\) nie nutne rôznych prvočísel \(p_1,\ p_2,\dots,\ p_n\), pre ktoré platí: \[\begin{aligned} p_1 &\mid p_2^2-1, \\ p_2 &\mid p_3^2-1, \\ &\vdots \\ p_{n-1} &\mid p_n^2-1, \\ p_n &\mid p_1^2-1.\end{aligned}\]
Poznámka. Zápis \(a \mid b\) čítame „\(a\) delí \(b\)“ a znamená, že existuje celé číslo \(k\) také, že \(a\cdot k=b\), čiže číslo \(b\) je deliteľné číslom \(a\).2
Pri deliteľnostiach s prvočíslami býva užitočné rozkladať veci na súčin. V tejto úlohe dokonca máme výrazy, ktoré na súčin idú rozložiť veľmi jednoducho. Pre každé \(i\) od \(1\) do \(n\) má platiť
\[\begin{aligned} p_i &\mid p_{i+1}^2-1, \\ p_i &\mid (p_{i+1}-1)(p_{i+1}+1).\end{aligned}\]
Indexy pritom berieme cyklicky, teda \(p_{n+1} = p_1\).
Teraz vieme využiť známu vlastnosť prvočísel, že ak prvočíslo delí súčin dvoch alebo viacerých činiteľov, tak musí deliť jedného z nich. Navyše platí (keďže naše čísla sú kladné), že deliteľ musí byť menší alebo rovný ako číslo, ktoré delí, teda \(p_i \leq p_{i+1}-1\), ak \(p_i\) delí prvú zátvorku alebo \(p_i \leq p_{i+1}+1\). Výhodnejšie však bude mať len jednu nerovnosť, a to \(p_i \leq p_{i+1}+1\), ktorá platí v každom prípade pre všetky \(i\).
Vidíme, že oba činitele, z ktorých jeden \(p_i\) delí, sú pre nepárne prvočíslo \(p_{i+1}\) párne. Oplatí sa teda úlohu rozdeliť podľa toho, či nejaké \(p_i\) je rovné \(2\).
Majme postupnosť prvočísel spĺňajúcu vzťahy zo zadania a skúmajme, aký môže byť počet týchto prvočísel \(n\). Predpokladajme najprv, že niektoré z prvočísel je rovné \(2\). Bez ujmy na všeobecnosti môžeme predpokladať, že \(p_n=2\). Keďže podmienky sa nezmenia, ak indexy prvočísel posunieme do kruhu, môžeme ich posunúť tak, aby dvojka (alebo jedna z viacerých dvojok) skončila na indexe \(n\).
Potom platí \(p_{n-1} \mid 2^2-1 = 3\), teda jediná možnosť, ako môže vyzerať predchádzajúce prvočíslo, je \(p_{n-1} = 3\). Pokračujme podobne ďalej, \(p_{n-2} \mid 3^2-1 = 8\). Jediné prvočíslo, ktoré delí \(8\), je \(2\), takže \(p_{n-2} = 2\). Opakuje sa nám situácia, v ktorej sme boli pre \(n\). Keď budeme tento postup opakovať, bude nám opakovane vychádzať, že jediná možnosť je, že postupnosť má tvar \(2,\ 3,\ 2,\ 3,\ 2,\ 3,\dots\).
Časom sa však potrebujeme dostať opäť k \(p_n\), ktoré je ale rovné \(2\). S párnym počtom prvočísel to funguje. Môžeme zobrať \(p_1 = p_3 = \dots = p_{n-1} = 3\) a \(p_2 = p_4 = \dots = p_n = 2\). Tieto prvočísla skutočne vyhovujú zadaniu.
Ak by však \(n\) bolo nepárne, dostali by sme, že \(p_n = p_{n-2} = \dots =p_1 = 2\), ale neplatí nám \(p_n \mid p_1^2-1\), pretože \(2 \not\mid 3\). To znamená, že pri nepárnom počte prvočísel dvojku nemáme.
Pre všetky \(i\) platí \(p_i \mid p_{i+1}-1\) alebo \(p_i \mid p_{i+1}+1\). Zároveň všetky \(p_i\) sú nepárne, a teda \(p_{i+1}-1\) aj \(p_{i+1}+1\) sú párne. Ak nepárne \(p_i\) delí niektorý z týchto výrazov, delí aj jeho polovicu. Ako sme už naznačili v úvode, \(p_i\) musí byť menšie alebo rovné ako to, čo delí, teda ako \(\frac{p_{i+1}-1}{2}\) alebo ako \(\frac{p_{i+1}+1}{2}\), v oboch prípadoch ale platí
\[\begin{aligned} p_i \leq \frac{p_{i+1}+1}{2}.\end{aligned}\]
Pre \(p_{i+1} \geq 3\) (všetky nepárne prvočísla sú väčšie alebo rovné \(3\)) nám platí, že \(\frac{p_{i+1}+1}{2} < p_{i+1}\), čo ľahko overíme roznásobením. Máme teda \(p_i \leq \frac{p_{i+1}+1}{2} < p_{i+1}\). Napísaním všetkých takýchto nerovností za seba dostaneme
\[\begin{aligned} p_1 < p_2 < p_3 < \dots < p_n < p_1,\end{aligned}\]
pretože podmienky platia cyklicky. Toto očividne nemôže nastať, pretože z toho vyplýva, že \(p_1 < p_1\).
Aj keď sa to možno nezdá, táto argumentácia funguje aj pre \(n=1\), pretože \(p_1\) delí \(p_1-1\) alebo \(p_1+1\) a z nepárnosti platí, že \(p_1 \leq \frac{p_1+1}{2} < p_1\), čo je rovnako ako vyššie spor.
Hľadané čísla \(n\) sú teda všetky kladné párne čísla.
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ť.