10. Kráľovná Matfyzu – Sušička vzorové riešenie

Dá sa celkom ľahko všimnúť, že funkcia \(f(n)=n\) vyhovuje zadaniu a keď sa nám nepodarí nájsť nejaké ďalšie, tak začneme mať podozrenie, že je jediná. Ukážeme, že zadaniu vyhovuje jedine funkcia \(f(n)=n\). Tak ako pri funkcionálkach býva zvykom, oplatí sa dosadiť na začiatok nejaké malé čísla, začneme s \(n=1,\ m=1\), \[\begin{aligned} 1+f(1)! &\mid f(1)!+f(1),\\ 1+f(1)! &\mid f(1)!+f(1)-(1+f(1)!),\\ 1+f(1)! &\mid f(1)-1.\end{aligned}\] Keďže \(f(1)-1\) je nezáporné, je to buď \(0\), alebo \(f(1)-1 \geq 1+f(1)!\). Druhá možnosť nemôže nastať, lebo \(f(1)! \geq f(1)\). Preto platí prvá možnosť \(f(1)-1=0,\ \ f(1)=1\).

Dosaďme ďalej len \(m=1\), \[\begin{aligned} n!+1 \mid f(n)!+1.\end{aligned}\]

Z tejto deliteľnosti máme \(f(n)! \geq n!\). Keďže faktoriál je rastúca funkcia, tak z toho vyplýva \(f(n) \geq n\).

Pokúsme sa z \((1)\) dokázať, že \(f(n)=n\). Nepodarí sa nám to zatiaľ pre všetky \(n\), ale len pre \(n=p-1\), kde \(p\) je prvočíslo. Keby bolo \(f(n)>n\) (vieme už, že \(f(n) \geq n\)), tak v \((1)\) by \(f(n)!\) bolo deliteľné číslom \(n+1\), teda pravá strana by nebola deliteľná \(n+1\). V prípade \(n=p-1\), \[(p-1)!+1 \mid f(p-1)!+1\] to znamená, že pravá strana by nebola deliteľná \(p\). Teraz si spomenieme na Wilsonovu vetu, ktorá hovorí, že \((p-1)! \equiv -1 \pmod{p}\), kde \(p\) je prvočíslo, teda \(p \mid (p-1)!+1\). Keďže \(p\) delí ľavú stranu deliteľnosti, tak \(p\) musí deliť aj pravú stranu. To je však v spore s povedaným vyššie. Preto \(f(p-1)=p-1\) pre všetky prvočísla \(p\).

Vráťme sa k pôvodnej deliteľnosti, \[\begin{aligned} n!+f(m)! &\mid f(n)!+f(m!),\nonumber\\ n!+f(m)! &\mid f(n)!+f(m!)-(n!+f(m)!),\nonumber\\ n!+f(m)! &\mid (f(n)!-n!)+(f(m!)-f(m)!).\end{aligned}\]

Zafixujme si \(m\) a za \(n\) dosádzajme do \((2)\) ľubovoľné \(p-1\). Zátvorka \((f(p-1)!-(p-1)!)\) bude vždy \(0\) a zátvorka \((f(m!)-f(m)!)\) je konštantná, lebo \(m\) sa nemení. Pravá strana deliteľnosti je konštantná, teda má len určitú konečnú ohraničenú množinu deliteľov, okrem prípadu, že \(0\) má nekonečne veľa deliteľov. Avšak ľavá môže byť ľubovoľne veľká – člen \((p-1)!\) je ľubovoľne veľký, lebo prvočísel je nekonečne veľa. To môže nastať, len keď pravá strana je \(0\), čiže \((f(m!)-f(m)!)=0\). Pre všetky \(m\) platí \(f(m!)=f(m)!\).

Teraz si zafixujme \(n\) a za \(m\) dosádzajme do \((2)\) ľubovoľne veľké čísla. Zátvorka \((f(m!)-f(m)!)\) je \(0\), pravá strana deliteľnosti je konštanta \((f(n)!-n!)\), ale ľavá strana môže byť ľubovoľne veľká kvôli členu \(f(m)!\). Preto \((f(n)!-n!)=0\), čiže \(f(n)!=n!\). Keďže faktoriál je rastúci, tak keď sa rovnajú dva faktoriály, tak sa rovnajú aj argumenty \(f(n)=n\). Premennú \(n\) sme mohli zafixovať na ľubovoľnej hodnote, takže sme dokázali, že pre všetky \(n\) platí \(f(n)=n\), čo je jediná vyhovujúca hľadaná funkcia.