Na konci dňa to už vyzeralo tak, že FKSáci sa nezhodnú. Adam sušičku vo FKS nechcel. Ale skúste sa hádať s Jarom, ktorý všetkých svojím mocným poradným hlasom presviedča, aby spravili nálet na T21 a sušičku im zobrali. Jaro pochopiteľne netušil, že sušička sa v tom čase nachádzala v KMSku. Nakoniec celé napätie vyvrcholilo až do bodu, kedy sa Adam rozhodol, že abdikuje z funkcie hlavného vedúceho. No, ale čo teraz? FKSáci možno získajú nazad sušičku, ale nie hlavného vedúceho. Môže sušička zastávať funkciu hlavného vedúceho ?
Nech $\mathbb{N}$ označuje množinu kladných celých čísel. Nájdite všetky funkcie $f:\mathbb{N}\rightarrow\mathbb{N}$ také, že $$n!+f(m)!\mid f(n)!+f(m!)$$ platí pre všetky $m,\,n\in\mathbb{N}$.
Miestnosť KSPákov ↩
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.
Korešpondenčný matematický seminár zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Intenzívny matematický zážitok v lete
Tímová matematická súťaž pre stredoškolákov
Knižnica všemožných matematických múdrostí