9. $k$-čka Mečmi Sekajú (vzorové riešenie) - Korešpondenčný matematický seminár

Zadanie

Vybrali sme sa po Hilbertovej štreke smerom do stredu Citadely. Prekročili sme živý plot a putovali sme mnoho dní, len aby sme sa opäť ocitli pred hradbami Citadely. Chcel som zaťať zuby a pokračovať v ceste, no Krutitruľo poklepal strážnika pred bránou po pleci a opýtal sa ho, kde je Kráľ Abstrakcie. Strážnik sa zaškeril a poznamenal, že kráľ sa chystá na vojnu a nemá čas riešiť chudákov. Krutitruľo toho holobriadka prehol na kolene a láskavo mu vysvetlil, že je svetoznámy stratég a kráľovi rád poskytne svoje služby. Tak sme sa ocitli v kráľovskej sále situovanej uprostred hrubých hradieb Citadely, kde nám šťúply mužíček vysvetlil, že proti nemu naraz vyrazili všetky prirodzené čísla a každé si najalo svoju armádu množín, a on sa obáva, či bude vedieť svojich nepriateľov spočítať.

Dokážte, že pre akékoľvek kladné celé číslo $k$ existuje iba konečne veľa $n$-tíc po dvoch rôznych prvočísel $p_1,p_2,\dots,p_n$ takých, že $(p_1+k)(p_2+k)\dots (p_n+k)$ je deliteľné $p_1p_2\dots p_n$.

Danú úlohu budeme riešiť sporom. Predpokladajme teda, že existuje nejaké kladné celé číslo $k$ také, že pre nekonečne veľa $n$-tíc po dvoch rôznych prvočísel $p_1, p_2, \dots ,p_n$ platí, že $p_1p_2 \dots p_n \mid (p_1+k)(p_2+k) \dots (p_n+k)$. Bez ujmy na všeobecnosti predpokladajme, že $p_1$ je najväčšie prvočíslo nejakej $n$-tice. Ak by sa nám podarilo hodnotu $p_1$ nejakým spôsobom zhora ohraničiť konkrétnou hodnotou $P$, tak už máme v podstate vyhraté. Isto totiž existuje iba konečne veľa $n$-tíc prvočísel menších ako $P$. Naším cieľom bude teda ďalej ukázať, že ak $p_1p_2 \dots p_n$ delí $(p_1+k)(p_2+k) \dots (p_n+k)$, tak $p_1 \leq 2k^2-k$.

Nech je $p_1>2k^2-k$ . Keďže $p_1$ je prvočíslo, ktoré delí súčin $(p_1+k)(p_2+k) \dots (p_n+k)$, musí deliť niektorú z daných zátvoriek. Prvočíslo $p_1$ určite nedelí zátvorku $p_1+k$, lebo $2p_1>p_1+k>p_1$, pretože platí $p_1>k$.

Bez ujmy na všeobecnosti nech $p_1$ delí zátvorku $(p_2+k)$. Keďže je však $p_1>2k^2-k$, tak určite $p_1>k$. Potom zrejme $2p_1>p_2+k$, keďže túto nerovnosť vieme získať sčítaním nerovností $p_1>p_2$ a $p_1>k$ (Zatiaľ predpokladajme, že $k>1$. Prípad $k=1$ potom ľahko doriešime neskôr). Ak má zároveň platiť, že dvojnásobok čísla $p_1$ je väčší ako $p_2+k$, ale zároveň $p_1$ delí $p_2+k$, tak zrejme $p_1=p_2+k$.

Podobnou úvahou zistíme, že prvočíslo $p_2$ musí deliť niektorú z daných zátvoriek. Prvočíslo $p_2$ určite nedelí zátvorku $p_1+k$. Keď je totiž $p_1>2k^2-k$ , tak platí, že $2p_2=2p_1-2k > p_1+k$, pretože platí $p_1>3k$ (zatiaľ predpokladajme, že $k>2$). Podobným spôsobom vieme zistiť, že $p_2$ nedelí zátvorku $p_2+k$.

Za predpokladu $p_1>2k^2-k$ sa vieme podobným spôsobom postupne dopracovať k tomu, že pre prvých $k$ prvočísel platí:

\[p_1=p_2+k=p_3+2k= \dots = p_k + (k-1)k.\]

Aby sme to však len tak neodmávali, overíme si toto naše tušenie indukciou. Náš indukčný predpoklad bude, že prvočíslo $p_i$ vieme zapísať ako $p_i= p_1 - (i-1)k$ a zároveň pre každé $j\leq i$ platí, že $p_j= p_1 - (j-1)k$, pričom $i \leq k$. (prvý indukčný krok je zrejmý: $p_1=p_1$).

Nech $j \leq i$. Ukážeme, že v takom prípade prvočíslo $p_i$ nedelí zátvorku $(p_j+k)$. Keď je totiž $p_1>2k^2-k$, tak platí:

\[p_1 > 2k^2 - k = (2k-1)k > (2i-j)k = 2(i-1)k - (j-1)k + k,\] \[2p_1 > p_1 + 2(i-1)k - (j-1)k + k,\] \[2p_i = 2(p_1-(i-1)k) > p_1 - (j-1)k + k = p_j+k,\] \[2p_i > p_j+k.\]

Vidíme, že dvojnásobok prvočísla $p_i$ je už väčší ako číslo $p_j+k$. Zároveň však ľahko vidíme, že musí platiť $p_i < p_j + k$. To zároveň implikuje, že musí naozaj existovať nejaké ďalšie prvočíslo také, že $p_i$ delí súčet tohto prvočísla s číslom $k$.

Bez ujmy na všeobecnosti nech teda $p_i$ delí $p_{i+1}+k$. Znovu ľahko ukážeme, že pre $p_1>2k^2-k$ platí (pričom majme stále na pamäti, že $i \leq k$):

\[p_1 > 2k^2-k>2ik-k,\] \[2p_1 > p_{i+1} + 2ik -k,\] \[2p_1-2(i-1)k>p_{i+1}+k,\] \[2p_i>p_{i+1}+k.\]

Keďže dvojnásobok prvočísla $p_i$ je väčší ako výraz $p_{i+1}+k$ a zároveň $p_i$ delí tento výraz, musí platiť, že $p_i=p_{i+1}+k$, z čoho už ľahko odvodíme:

\[p_{i+1}= p_i - k= p_1 - (i-1)k -k = p_1 -ik,\] \[p_{i+1}=p_1-ik.\]

Čím sme našu indukciu úspešne dokončili a máme:

\[p_1=p_2+k=p_3+2k= \dots = p_k + (k-1)k.\]

Predpokladajme, že by nejaké dve čísla $p_i$ a $p_j$ z našej $k$-tice mali rovnaký zvyšok po delení $k-1$. BUNV predpokladajme, že $i \geq j$. Potom platí, že výraz $k-1$ musí deliť $p_j-p_i$,

\[\begin{aligned} (k-1) &\mid p_j - p_i, \\ (k-1) &\mid p_1 - (j-1)k - p_1 + (i-1)k, \\ (k-1) &\mid (i-j)k.\end{aligned}\]

Čísla $k-1$ a $k$ sú nesúdeliteľné. Potom zrejme výraz $k-1$ musí deliť rozdiel $i-j$. Všimnime si ale, že čísla $i,j$ sú z množiny ${1,2 \dots k-1}$, z čoho jasne vyplýva, že $i=j$. Vidíme, že medzi prvočíslami $p_1, p_2, \dots p_k$ teda nie sú žiadne dve prvočísla, ktoré by mali rovnaký zvyšok po delení $k-1$. Máme $k-1$ prvočísel a z nich každé má iný zvyšok po delení $k-1$. Niektoré z nich potom musí dávať zvyšok $0$ po delení $k-1$. Za predpokladu, že $k>2$ to však znamená, že dané číslo nie je prvočíslo.

Ostáva nám už len poriešiť prípady, keď $k=1$, alebo $k=2$.

Pokiaľ $k=1$, tak ľahko vidíme, že vyhovuje iba jedna $n$-tica prvočísel ($p_1=3$ a $p_2=2$).

Pokiaľ $k=2$ vyhovuje tiež iba jedna $n$-tica ($p_1=7$, $p_2=5$, $p_3=3$). Ľahko totiž odvodíme, že musí platiť $p_1=p_2+2=p_3+4$. Rozmyslite si, že práve jedno z týchto troch čísel musí byť deliteľné tromi.

Dokázali sme, že hodnota $p_1$ nemôže byť väčšia ako $k^2-k$. Tým pádom je hodnota najväčšieho z prvočísel v danej $n$-tici ohraničená zhora, z čoho už jasne vyplýva, že nemôže existovať nekonečne veľa takých $n$-tíc.

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ť.

9. $k$-čka Mečmi Sekajú vzorové riešenie

Zadanie

Diskusia