8. Kučeravý Maťko Sklerotický vzorové riešenie

I keď to nie je úplne funkcionálna rovnica, lebo nemáme žiadnu rovnosť :), tak stále máme k dispozícii nejaký vzťah, ktorý platí pre všetky prirodzené čísla \(m\), \(n\). Môžeme preto zvoliť nejaké konkrétne a pozrieť sa, ako vyzerá podmienka pre ne. Pracujeme na prirodzených číslach, a preto, žiaľ, nuly dosadiť nemôžeme. Môžeme však dosadiť \(m=n=1\). Dostávame, že \(1+f(1)\mid 2f(1)\). Z tohto nám vyplýva, že \(1+f(1)\mid 2f(1)-(1+f(1))=f(1)-1\), no keďže zjavne \(1+f(1)>f(1)-1\ge 0\), tak na to, aby to platilo, musí byť \(f(1)-1=0\). Fajn, vypočítali sme, že \(f(1)=1\).

To by sme chceli nejako využiť, a preto dosadíme \(m=1\) (pretože \(n=1\) by nám už nedalo nič nové). Máme \(n+1\mid f(n)+n\) \((\diamondsuit)\).

Ok, to vyzerá, že sa môže hodiť, ale zatiaľ nám to nejak veľa nehovorí. Skúsme preto iné dosadenie. Ponúka sa dosadiť \(m=n\). Dostávame \(n+f(n)\mid f(n)+nf(n)\). My však vieme, že \(n+f(n)\mid n^2+nf(n)\). Po odčítaní týchto dvoch vzťahov máme \(n+f(n)\mid n^2-f(n)\). Môžeme si všimnúť, že keby \(n^2-f(n)\) bolo záporné (t.j. \(f(n)>n^2\), tak určite \(|n+f(n)|>f(n)>f(n)-n^2=|n^2-f(n)|\). To by ale bol spor s našou deliteľnosťou. Preto \(f(n)\le n^2\) \((\heartsuit)\) , pre všetky prirodzené \(n\).

Hodnotu \(f(1)\) sme už vypočítali. Môžeme sa pozrieť, čo to hovorí pre \(f(2)\). Vieme, že \(f(2)\le 4\), takže máme len 4 možnosti. Navyše vieme, že \(3\mid f(2)+2\). Z týchto dvoch podmienok máme už len dve možnosti: \(f(2)=1\) alebo \(f(2)=4\).

Tak skúsme predpokladať, že \(f(2)=1\) a dosadiť \(n=2\). Dostávame, že \(2+f(m)\mid 1+2f(m)\). To vieme upraviť na \(2+f(m)\mid 3\). Avšak \(2+f(m)\ge 3\), tak z toho dostávame, že nutne \(f(m)=1\), pre všetky prirodzené čísla \(m\).

Vidíme, že v prípade \(f(2)=1\) dostávame konštantnú jednotkovú funkciu. Ľahko skúškou overíme, že naozaj vyhovuje.

Ďalej prepokladajme, že \(f(2)=4\). Tu to už bude ťažšie, ale ak skúsime dosadiť ďalšie malé čísla, môžeme prísť na hypotézu, že by mohlo platiť \(f(n)=n^2\). Na funkcionálky nad \(\mathbb{N}\) je často dobrá indukcia. Skúsme to dokázať indukciou. Prvý krok (pre \(n=1\) a \(n=2\)) sme už urobili. Predpokladajme, že \(f(k)=k^2\) a dokážme to aj pre \(k+1\).

Urobíme to priamočiaro – proste dosadíme \(m=k\) a \(n=k+1\). Dostávame \[ \begin{aligned} k+1+k^2 &\mid f(k+1)+(k+1)k^2\Rightarrow \\ \Rightarrow 1+k+k^2&\mid f(k+1)+(k+1)k^2-k(1+k+k^2)=f(k+1)-k. \end{aligned} \]

My však vieme z \((\heartsuit)\), že \(f(k+1)\le (k+1)^2\). (Vidíte, ako sa zrazu tie zistenia z triviálnych dosadení zídu?) Preto máme len 2 možnosti. Buď \(f(k+1)=k\) alebo \(f(k+1)=k+(1+k+k^2)=(k+1)^2\), keďže ďalšie číslo so zvyškom \(k\) po delení \((1+k+k^2)\) by už bolo veľké. No prípad \(f(k+1)=k\) vylúčime tak, že z \((\diamondsuit)\) vieme, že \(k+2\mid f(k+1)+k+1\). A keby \(f(k+1)=k\), tak máme \(k+2\mid 2k+1\), čo je ekvivalentné s \(k+2\mid 3\). A to pre \(k\ge 2\) už neplatí, čo je spor. Preto nutne \(f(k+1)=(k+1)^2\).

To je záver dôkazu indukciou, a preto pre všetky prirodzené čísla platí, že \(f(n)=n^2\). Skúškou ľahko overíme, že aj táto funkcia vyhovuje.

Úloha má 2 riešenia, a to \(f(n)=1\) a \(f(n)=n^2\).

Iné riešenie

Teraz si ukážeme trocha vyspelejšie riešenie, v ktorom sa nebudeme babrať s dosadzovaním jednotiek a iných malých čísel. Všimnime si, že aj v predošlom riešení, sme deliteľnosť často upravovali na lepší tvar. To môžeme urobiť hneď na začiatku. Vieme, že \(n+f(m)\mid f(n)+nf(m)\). Ak od ľavej strany odčítame \(n(n+f(m))\), tak dostaneme, že \(n+f(m)\mid f(n)-n^2\).

Do tohto vzťahu zase nič nedosadíme, len si uvedomíme, čo nám hovorí. A čo nám hovorí? Nuž, ak zafixujeme \(n\), tak pravá strana sa zafixuje tiež. Ak ak \(f(n)-n^2\neq 0\), tak má len konečný počet deliteľov. To znamená, že \(n+f(m)\) môže nadobúdať iba konečný počet hodnôt a preto je nutne \(f(m)\) ohraničená.

To celé za predpokladu, že \(f(n)\neq n^2\). Lenže my môžeme \(n\) zvoliť ľubovoľne, a preto platí, že buď je \(f\) ohraničená alebo \(f(n)=n^2\) pre všetky \(n\).

Našli sme jedno riešenie a ďalej už môžeme riešiť len prípad, že \(f(n)\le C\), pre všetky \(n\) a nejakú konštantu \(C\).

Skúsime teraz vzťah zo zadania upraviť inak: \[n+f(m)\mid f(n)+nf(m)-f(m)(n+f(m))=f(n)-f(m)^2\]. No my vieme, že \(f\) je ohraničená, preto celá pravá strana je ohraničená. Avšak ľavá strana ohraničená nie je. Ak teda zvolíme dostatočne veľké \(n\), napr. \(n=n_0=C^2+47\), tak určite bude platiť, že \(|n_0+f(m)|>|f(n_0)-f(m)^2|\), a teda nutne \(f(n_0)-f(m)^2=0\). Toto platí pre všetky \(m\), a preto \(f\) je konštanta. Navyše to platí aj pre \(m=n_0\), a preto vieme dopočítať, že táto konštanta je rovná \(1\).

Zistili sme, že ak je \(f\) ohraničená, tak nutne \(f(n)=1\) pre všetky \(n\). A samozrejme ešte tak isto ako v predošlom riešení, treba urobiť skúšku pre obidve nájdené riešenia.

 Komentár

Vieme, že \(a\mid b\) z definície vtedy, ak existuje celé číslo \(k\) také, že \(ak=b\). Avšak používať toto \(k\) na nejaké dôkazy skoro nikdy nie je na nič dobré (OK, ak robíte Vieta jumping, tak sa hodí). Z deliteľnosťami sa dá dobre, ľahšie a efektívnejšie manipulovať bez pomoci tohto \(k\) odčítaním nejakých násobkov ľavej strany k pravej, tak ako to bolo robené veľakrát vo vzorovom riešení. Preto vám odporúčam, aby ste ho do budúcna nepoužívali. Je to zhruba taká rada, ako to, že si do geometrického obrázka NEkreslite stred kružnice, pokiaľ nie je zadaný.

A ak túto radu nedodržíte a použijete ho, tak určite nemôžete predpokladať, že \(k\) je rovnaké pre všetky možné deliteľnosti :) (Ak sa pri tomto smejete, tak vedzte, že takúto chybu urobila veľká časť z vás.)