Zadanie
Ako vedúci a účastníci prechádzali ponad Poprad1 a popod Tatry, tešili sa na krásne výhľady. Nepríjemne ich preto prekvapila protihluková stena, ktorá sa stále zvyšovala a stále viac a viac im uberala z výhľadu na malebné hory a slnečný svit aj Svit. Začalo ich preto zaujímať, akú funkciu má taká vysoká protihluková stena a aká najmenej vysoká musela byť.
Nech \(f\) je funkcia z kladných celých čísel do kladných celých čísel spĺňajúca
\(f(ab)=f(a)f(b)\) pre všetky celé kladné čísla \(a\), \(b\),
\(f(a)<f(b)\) pre všetky \(a<b\),
\(f(3)\geq 7\).
Nájdite najmenšiu možnú hodnotu, ktorú môže nadobúdať \(f(3)\).
rieku↩
Zadanie na prvý pohľad môže vyznievať ba priam až nezmyselne jednoducho. Máme nájsť najmenšiu možnú hodnotu \(f(3)\), pričom zároveň tretia podmienka nám hovorí, že \(f(3)\geq7\). Tak potom najmenšia možná hodnota \(f(3)\) je \(7\), nie?
No a tu prichádza ten zvrat. Hodnota \(f(3)=7\) je síce najmenšia hodnota, ktorá nie je v rozpore s treťou z podmienok. No pokiaľ budeme hľadať funkciu, ktorá bude spĺňať všetky tri podmienky, nemusí sa nám podariť nájsť takú, že \(f(3)=7\).
No a čo je to vlastne funkcia? To sú dvojice (vzor, obraz), pričom funkciu vieme vnímať ako „stroj“, do ktorého „vhodíme“ vzor, funkcia sa pozrie, aký má k tomuto vzoru priradený obraz a „vyhodí“ tento obraz.
Funkcie môžu vyzerať všelijako. Môžu byť jednoduché, napríklad
taká, ktorá vyhodí to isté číslo, ktoré sme do nej hodili,
taká, ktorá zvýši vhodené číslo o \(1\) a vyhodí výsledok,
taká, ktorá vyhodí \(42\) bez ohľadu na to, ktoré číslo sme do nej vhodili.
Funkciami sú však napríklad aj
taká, ktorá pre vhodené číslo \(x\) vyhodí najmenšie číslo, ktoré má práve \(x\) deliteľov,
taká, ktorá pre vhodené číslo \(x\) nájde \(x\)-té slovo v Sládkovičovej Maríne (ak je \(x\) priveľké a dostane sa až na koniec, pokračuje ďalej od začiatku) a vyhodí počet písmen v ňom,
taká, ktorá vyhodí \(42\), ak sme do nej vhodili číslo z prvočíselnej dvojičky1 a \(17\) inak.
Tie z prvej skupiny by sme vedeli pomerne jednoducho popísať operáciami plus, mínus, krát, atď., no tie z druhej skupiny už veľmi nie. Dokonca o poslednej z nich ani nevieme povedať, ako sa správa, lebo keby sme to vedeli, vyriešili by sme otvorený problém. Argumentácia tým, že prešetríme všetky možnosti, ako môže vyzerať predpis funkcie, preto nefunguje, lebo nie každá funkcia je definovaná jednoduchým vzorčekom.
Ale teraz späť k úlohe. Povedzme, že \(f(3)\) by mohlo byť \(7\). Čo vieme povedať ďalej? No napríklad, že \(f(9)=f(3\cdot3)=f(3)\cdot f(3)=49\). Podobne dostaneme aj, že \(f(27)=343\). Čo ale vieme o hodnote \(f(2)\)? Funkcia musí byť rastúca, preto \(f(2)<f(3)=7\), a teda \(f(2)\) je najviac \(6\). Zároveň \(7=f(3)<f(4)=f(2)\cdot f(2)\). Z tohto zas vidíme, že \(f(2)\) musí byť aspoň \(3\). Ak by totiž hodnota \(f(2)\) bola \(1\) alebo \(2\), potom by \(f(4)\) bolo \(1\) alebo \(4\), čo je však menej ako \(7\), a teda by naša funkcia nerástla.
Aktuálne sú teda možné hodnoty \(f(2)\) čísla \(3, 4, 5\) a \(6\). Skúsme nájsť ešte nejaké blízke mocniny dvojky a trojky, aby sme vedeli viac okresať možnosti na hodnotu \(f(2)\). Najbližšie máme \(8\) a \(9\), pričom vieme, že \(f(2)\cdot f(2)\cdot f(2)=f(8)<f(9)=49\). Ak by \(f(2)\) bolo \(4\) alebo viac, tak \(f(2)^3\) je \(64\) alebo viac, čo je ale viac ako \(49\). Preto je aktuálne jediná prípustná hodnota \(f(2)\) rovná \(3\). Skúsme však ešte overiť, či sa to nepokazí pre nejaké vyššie mocniny. Napríklad \(27\) a \(32\). Vieme, že \(f(27)\) je \(343\). To musí byť menšie ako \(f(32)=f(2)\cdot f(2)\cdot f(2)\cdot f(2)\cdot f(2)\), čo však v prípade, že \(f(2)\) je rovné trom, vychádza \(243\). No a \(343\) nie je ani zďaleka menšie ako \(243\), čiže ani \(f(2)=3\) nemôže platiť.
Keď sme teda skúsili nájsť takú funkciu, že \(f(3)=7\), dospeli sme k tomu, že akákoľvek hodnota \(f(2)\) by viedla k rozporu či už s prvou alebo druhou podmienkou zadania. Preto nie je možné, aby \(f(3)\) mala hodnotu \(7\).
Veľmi podobne by to skončilo, aj keby sme skúsili, že \(f(3)=8\). Totiž, potom \(f(9)=64\) a \(f(27)=512\). Zo vzťahu \(f(27)\) a \(f(32)\) vieme, že \(f(2)^5=f(32)>f(27)=512\), a teda \(f(2)\geq4\). Porovnaním \(f(8)\) a \(f(9)\) naopak dostávame, že \(f(2)^3=f(8)<f(9)=64\), čiže \(f(2)<4\), čo je dokopy spor.
No a keď by sme začali s predpokladom, že \(f(3)=9\), podobne ako vyššie by sme
vzťahom medzi \(f(2)\) a \(f(3)\) dostali, že \(f(2)\leq 8\),
vzťahom medzi \(f(3)\) a \(f(4)\) dostali, že \(f(2)\geq 4\) a
vzťahom medzi \(f(8)\) a \(f(9)\) zas, že \(f(2)\leq 4\).
Čiže \(f(2)\) môže byť jedine \(4\). Toto by nám už však nikde vyššie rozpory nespôsobovalo. Tiež by sme mohli skúšať, čo vieme zistiť o \(f(5)\), no a postupne by sme povylučovali všetky možnosti okrem čísla \(25\). No a tu si už začneme všímať, že nám vychádzajú druhé mocniny čísla, ktoré do funkcie vhodíme.
Javí sa to teda tak, že funkcia \(f(x)=x^2\) bude vyhovovať pre hodnotu \(f(3)=9\). Overme ešte, že naozaj spĺňa všetky tri podmienky zadania. To je však zrejmé, lebo
\(f(ab)=(ab)^2=a^2b^2=f(a)f(b)\),
ak \(a<b\), tak keďže \(a, b\) sú kladné, tak následne aj \(f(a)=a^2=a\cdot a<a\cdot b<b\cdot b=b^2=f(b)\),
\(f(3)=3^2=9\geq7\).
Dostali sme teda, že \(f(3)\) nemôže byť \(7\) ani \(8\) (lebo následne sme ukázali, že neexistuje vhodná hodnota pre \(f(2)\)) a potom sme prišli na to, že \(f(3)=9\) vieme dosiahnuť s funkciou \(f(x)=x^2\). To znamená, že najmenšia možná hodnota \(f(3)\) je deväť2.
Poznámka k riešeniam využívajúcim ťažké kalibre
Ako sa dá zo vzorového riešenia vidieť, úloha sa dala vyriešiť pomerne jednoducho a bez použitia náročných techník a viet. Vyskytlo sa však zopár riešení, ktoré sa snažili použiť na úlohu nejaké silné tvrdenia ako Cauchyho multiplikatívnu funkcionálnu rovnicu3 alebo Erdősovu vetu4. Obidve nejakým spôsobom tvrdia, že ak máme multiplikatívnu funkciu (\(f(ab)=f(a)f(b)\)), tak riešenia sú tvaru \(f(x)=x^\alpha\). Keď hovorím „nejakým spôsobom“, myslím tým, že za obidvoma z nich sa skrýva niekoľko zádrheľov, kvôli ktorým nemôžete ani jednu z viet priamo použiť na úlohu. Poväčšine sa vám nepodarilo tieto zádrhele vyriešiť tak, aby sa na úlohu veta naozaj dala použiť.
Pri Cauchyho funkcionálke to ani nebolo možné. Totiž, ako sa môžete dočítať na uvedenej stránke, ide o funkciu, ktorá každému kladnému reálnemu číslu priradzuje nejaké kladné reálne číslo. Zároveň sa vyžaduje, aby bola spojitá. Funkcie z kladných reálnych čísel sú niečo úplne iné ako funkcie z kladných celých čísel. To, že máme nejaké riešenie na celočíselných funkciách, nemusí nutne znamenať, že toto riešenie ide rozšíriť či zovšeobecniť aj na reálnu funkciu. Navyše, Cauchyho funkcionálna rovnica má aj množstvo nespojitých riešení, ktoré nie sú tvaru \(f(x)=x^\alpha\). Čo s nimi?
Čo sa týka Erdősovej vety, tá už bola trochu uchopiteľnejšia. Hovorí totiž o funkciách, ktoré zobrazujú z prirodzených čísel do reálnych čísel a tvrdí, že riešenia sú tvaru \(f(x)=x^\alpha\), kde \(\alpha\) je reálna konštanta. Už sa teda funkcie aspoň zhodujú v tom, čo do nich môžeme vhadzovať. Niektorí z vás však bez bližšieho zdôvodnenia povedali, že keďže pre \(\alpha=1\) je \(f(3)\) ešte menšie ako \(7\) a pre \(\alpha=2\) už je to \(9\), tak \(f(3)\) musí byť aspoň \(9\). Lenže, \(\alpha\) je reálna konštanta, prečo by to nemohlo byť nejaké číslo medzi \(1\) a \(2\), napríklad \(\frac\pi2\)? Ono to síce intuitívne vyzerá tak, že na to, aby sme vždy ako výsledok funkcie dostali celé číslo, musí byť aj exponent celý, no ale chcelo by to aj dokázať. A to vo všeobecnosti nie je ľahké, lebo veď, ani umocňovanie na iracionálne čísla nie je ľahké. A ako sa teda dalo za riešenie s Erdősovou vetou získať \(9\) bodov?
Korektné riešenie využívajúce Erdősovu vetu (inšpirované riešením Samuela Vargovčíka)
Z Erdősovej vety vieme, že ak nejaká funkcia spĺňa všetky tri podmienky zadania, musí pre ňu existovať reálna konštanta \(k\) taká, že \(f(x)=x^k\). Zaujímajú nás len prípady, kedy \(f(3)<9\), keďže z predošlého riešenia už vieme, že \(f(3)\) môže byť \(9\). Z tretej podmienky vyplýva \(f(3)\ge7\), a keďže \(f(3)\in\mathbb Z^+\), ostáva prešetriť prípady \(f(3)=7\) a \(f(3)=8\), teda \(k=\log_3 7\) a \(k=\log_3 8\). To, že tieto \(k\) nefungujú, vyplýva z toho, že pre ne \(f(2)=2^k\) nie je celé číslo, pretože \(3<2^k<4\). Poďme to dokázať.
Vieme, že \(3^5=243<343=7^3\). Keďže tretia odmocnina je rastúca funkcia, môžeme obe strany odmocniť a vzťah sa nezmení, čiže \(3^\frac{5}{3}<7\). Teraz dvakrát za sebou využijeme, že logaritmus so základom \(3\) je tiež rastúca funkcia. Prvýkrát na to, aby sme predošlý vzťah mohli zlogaritmovať a dostať \(\frac{5}{3}<\log_3 7\) a druhýkrát na to, aby sme mohli prireťaziť do nerovnosti ďalšie hodnoty, konkrétne \(\frac{5}{3}<\log_3 7<\log_3 8<\log_3 9=2\).
Vidíme teda, že ak by \(f(3)\in\{7,8\}\), tak \(\frac53<k<2\). Ďalej vieme, že \(\left(\frac{3}{2}\right)^3=\frac{27}{8}<4=2^2\). Treťou odmocninou dostávame \(\frac32<2^\frac23\), vďaka čomu už vieme s rastúcosťou exponenciálnej funkcie so základom \(2\) ľahko nahliadnuť, že naozaj \(2^k<2^2=4\) a \(2^k>2^\frac53=2\cdot2^\frac23>2\cdot\frac32=3\).
Preto, ak by \(k\) zodpovedalo hodnotám \(f(3)=7\) alebo \(f(3)=8\), tak \(f(2)=2^k\) nemôže byť kladné celé číslo, spor. To znamená, že \(f(3)\) nemôže byť \(7\) ani \(8\), triviálne nemôže byť menšie než \(7\) a musí byť celé číslo, takže musí byť aspoň \(9\). Keďže môže byť presne \(9\), najmenšia hodnota, ktorú môže nadobúdať \(f(3)\), je \(9\).
https://cs.wikipedia.org/wiki/Prvo%C4%8D%C3%ADseln%C3%A1_dvojice↩
Jožtek by vám to isto s radosťou povedal, keby ste sa ho na to opýtali↩
https://imomath.com/index.cgi?page=cauchyFunctionalEquations, posledná odrážka↩
https://ak2316.user.srcf.net/2021/09/erdos-monotone-multiplicative/↩
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ť.