Az A. 880. feladat (2024. április)

A. 880. Határozzuk meg az összes \(\displaystyle (a,b,c)\) valós számokból álló számhármast, amelyre létezik olyan \(\displaystyle f\colon\mathbb{Z}^+ \to \mathbb{Z}^+\) függvény, hogy

\(\displaystyle af(n)+bf(n+1)+cf(n+2)<0 \)

minden \(\displaystyle n \in \mathbb{Z}^+\) számra (\(\displaystyle \mathbb{Z}^+\) a pozitív egész számok halmazát jelöli).

Javasolta: Imolay András (Budapest)

(7 pont)

A beküldési határidő 2024. május 10-én LEJÁRT.

Megoldás. Nevezzünk egy \(\displaystyle (a,b,c)\) valós számokból álló számhármast szépnek, ha teljesül rá a feladat feltétele, azaz létezik megfelelő függvény.

1. eset: \(\displaystyle c<0\).

Azt állítjuk, hogy ekkor bármilyen \(\displaystyle a,b \in \mathbb{R}\) számok esetén \(\displaystyle (a,b,c)\) szép. Ehhez mutatnunk kell egy megfelelő \(\displaystyle f\) függvényt. Definiáljuk sorba az értékeit: amikor az \(\displaystyle (n+2).\) értéket definiáljuk, arra figyelünk, hogy az \(\displaystyle n.\) elvárt egyenlet teljesüljön. Legyen \(\displaystyle f(1)=f(2)=1\). Most tegyük fel, hogy már az \(\displaystyle f(1), f(2), \ldots , f(n+1)\) értékeket definiáltuk úgy, hogy minden \(\displaystyle k \leq n-1\) esetén teljesül, hogy \(\displaystyle af(k)+bf(k+1)+cf(k+2)<0\). Legyen most \(\displaystyle f(n+2)\) olyan nagy, hogy \(\displaystyle |cf(n+2)|>af(n)+bf(n+1)\). Ilyet nyilván tudunk választani, mert \(\displaystyle c \neq 0\), és mivel \(\displaystyle c<0\), így teljesülni fog az \(\displaystyle n.\) egyenlet, pont ahogy akartuk.

2. eset: \(\displaystyle c=0\).

Azt állítjuk, hogy ekkor \(\displaystyle (a,b,c)\) pontosan akkor szép, ha \(\displaystyle b<0\) vagy \(\displaystyle a+b<0\). Ha az előbbi teljesül, akkor az előző esethez hasonlóan minden \(\displaystyle n\)-re tudok sorba definiálni egy \(\displaystyle f(n)\) értéket úgy, hogy \(\displaystyle f(n+1)\) olyan nagy legyen, hogy \(\displaystyle |bf(n+1)|>af(n)\), ami egy megfelelő függvényt ad. Utóbbi esetben, ha \(\displaystyle a+b<0\), akkor a konstans 1 függvény megfelelő.

Tehát már csak azt kell megmutatnunk, hogy ha \(\displaystyle b \geq 0\) és \(\displaystyle a+b \geq 0\), akkor nincs megfelelő függvény. Ha \(\displaystyle a \geq 0\), akkor ez világos, különben vegyük észre, hogy

\(\displaystyle 0>af(n)+bf(n+1)=-a(f(n+1)-f(n))+(a+b)f(n+1).\)

Az utolsó tag nemnegatív, és \(\displaystyle a<0\), így ekkor \(\displaystyle f(n+1)-f(n)<0\), azaz a függvény szigorúan monoton csökken, ám ez nem lehetséges egy pozitív egészekbe képző függvénynél.

3. eset \(\displaystyle c>0\).

3.1. eset \(\displaystyle a \leq 0\).

Azt állítjuk, hogy ebben az esetben pontosan akkor lesz \(\displaystyle (a,b,c)\) szép, ha \(\displaystyle a+b+c<0\). Világos, hogy ebben az esetben tényleg szép, mert a konstans 1 függvény megfelelő. Tegyük most fel, hogy \(\displaystyle a+b+c \geq 0\). Adjuk össze az első \(\displaystyle n\) egyenletet:

\(\displaystyle af(1)+(a+b)f(2)+\sum_{i=3}^n((a+b+c)f(i))+(b+c)f(n+1)+cf(n+2)<0.\)

Figyeljük meg, hogy \(\displaystyle a+b+c \geq 0\) miatt a szummás tag nemnegatív, és \(\displaystyle a \leq 0\) miatt \(\displaystyle b+c \geq 0\), így \(\displaystyle 0 \leq (b+c)f(n+1)\), sőt, tudjuk, hogy \(\displaystyle c>0\), így \(\displaystyle cf(n+2)>0\). Tehát az egyenlet bal oldalán csak az első két tag lehet negatív, ám ezek a tagok nem függnek \(\displaystyle n\)-től. Emiatt, mivel a fenti egyenlőtlenség mindig igaz (tegyük fel, hogy \(\displaystyle n \geq 3\), hogy biztosan megjelenjen mind az öt tag a fenti képletben), \(\displaystyle f(n+2)<-af(1)-(a+b)f(2)\) minden \(\displaystyle n \geq 3\) esetén, azaz \(\displaystyle f\) felülről korlátos. Ez azt is jelenti, hogy csak véges sok \(\displaystyle (f(k),f(k+1),f(k+2))\) különböző számhármas van, így az \(\displaystyle af(k)+bf(k+1)+cf(k+2)\) kifejezésnek van egy \(\displaystyle t<0\) maximuma. Ám ekkor újra felírhatjuk az első \(\displaystyle n\) egyenlet összegét, a felső becslés helyett beírva ezt az erősebb becslést:

\(\displaystyle af(1)+(a+b)f(2)+\sum_{i=3}^n((a+b+c)f(i))+(b+c)f(n+1)+cf(n+2) \leq nt.\)

Ez pedig már könnyen ellentomndásra vezet, mivel láttuk, hogy a bal oldalon csak az első két tag lehet negatív, és azok nem függnek \(\displaystyle n\)-től, míg a jobb oldal bármilyen kicsi lehet, ha \(\displaystyle n\) elég nagy.

3.2. eset \(\displaystyle a > 0\).

Világos, hogy ha \(\displaystyle b \geq 0\), akkor nincs megfelelő függvény, így mostantól feltesszük, hogy \(\displaystyle b<0\). Ezt további két esetre bontjuk.

3.2.1. eset \(\displaystyle c \geq a\).

Azt állítjuk, hogy ebben az esetben pontosan akkor lesz megoldás, ha \(\displaystyle a+b+c<0\). Mint már láttuk, ilyen esetben triviálisan jó például a konstans 1 függvény. Ha \(\displaystyle a+b+c \geq 0\), akkor rendezzük át az eredeti függvényegyenlőtlenséget:

\(\displaystyle 0>af(n)+bf(n+1)+cf(n+2)=a(f(n)-f(n+1))+c(f(n+2)-f(n+1))+(a+b+c)f(n+1) \geq\)

\(\displaystyle \geq a(f(n)-f(n+1))+c(f(n+2)-f(n+1)).\)

Legyen \(\displaystyle g(n)=f(n+1)-f(n)\), ezt a fenti egyenletbe beírva, és rendezve kapjuk, hogy \(\displaystyle ag(n)>cg(n+1).\) Mivel \(\displaystyle c \ge a >0\), ebből következik, hogy \(\displaystyle g\) szigorúan monoton csökken. Mivel az értékei egészek, ez azt jelenti, hogy valahonnan kezdve negatív, ez pedig \(\displaystyle f\)-re nézve azt jelenti, hogy valahonnan kezdve szigorúan monoton csökkenő. Ez viszont nem lehetséges egy pozitív egészekbe képző függvénynél.

3.2.2. eset \(\displaystyle a>c\).

Motiváció: Az összes közül ez a legnehezebb eset, és ha az ember csak elolvassa a megoldást, nagyon hasraütésszerűnek tűnhet, hogy miért éppen ezt csináljuk, erről írunk itt most néhány szót. A kulcs gondolat, hogy \(\displaystyle f(n)=s^n\) alakú exponenciális függvényekkel akarunk próbálkozni. Erre a gondolatra több motiváció is van. Egyrészt (ahogy a lináris rekurziók elméletébe is így kerülnek be az exponenciális függvények), ha ilyen alakú \(\displaystyle f\) függvényeket keresünk, akkor a végtelen sok egyenletünk helyett csak egy marad. Mivel ugye azt kell látni, hogy minden \(\displaystyle n\)-re \(\displaystyle af(n)+bf(n+1)+cf(n+2)<0\), ám ebbe beírva az \(\displaystyle s^n\) függvényt, majd \(\displaystyle s^n\)-nel egyszerűsítve azt kapjuk, hogy az \(\displaystyle a+bs+cs^2<0\) egyenlőtlenségnek kell teljesülnie, és ha ez teljesül, akkor teljesül a függvényegyenlőtlenség minden \(\displaystyle n\)-re. Másrészt, ha az ember vizsgálgatja a 3.1 esetben megjelenő összegzést, és felteszi, hogy \(\displaystyle a+b+c>0\), akkor érezhető, hogy ahhoz, hogy a nagy szummás tag (ami pozitív) ne győzze le a \(\displaystyle (b+c)f(n+1)\) tagot, ahhoz az \(\displaystyle f\)-nek nagyon gyorsan (exponenciálisan) kell nőnie. Ezek után, ha \(\displaystyle a\) és \(\displaystyle c\) fix, akkor be lehet írni, hogy melyik \(\displaystyle s\) esetén adja az \(\displaystyle f(n)=s^n\) a lehető legjobb \(\displaystyle b\)-t, és (például deriválással) egyszerűen kapható, hogy éppen az \(\displaystyle s=\frac{\sqrt{a}}{\sqrt{c}}\) lesz az a szám, melyre \(\displaystyle b\) a lehető legnagyobb, hogy \(\displaystyle a+bs+cs^2=0\), és ekkor \(\displaystyle b=-2\sqrt{ac}\). Még innen sem egyszerű befejezni, de talán most már motiváltabb, hogy miért a következőkben leírtakat csináljuk. Íme a megoldás:

Azt állítjuk, hogy \(\displaystyle (a,b,c)\) pontosan akkor lesz szép, ha \(\displaystyle b \leq -2\sqrt{ac}\). Világos, hogy ha \(\displaystyle f\) egy megfelelő függvény \(\displaystyle (a,b,c)\)-hez, akkor \(\displaystyle (a,b',c)\)-hez is, ahol \(\displaystyle b' \leq b\), így elég konstrukciót mutatunk az \(\displaystyle (a,-2\sqrt{ac},c)\) hármasra, hogy belássuk, hogy \(\displaystyle (a,b,c)\) szép, ha \(\displaystyle b \leq -2\sqrt{ac}\). Legyen \(\displaystyle s=\frac{\sqrt{a}}{\sqrt{c}}\). Tudjuk, hogy \(\displaystyle a \neq c\), így szigorúan teljesül rájuk a számtani-mértani egyenlőtlenség, azaz \(\displaystyle a+c+b=a+c-2\sqrt{ac}>0\). Legyen \(\displaystyle N\) egy olyan egész szám, melyre \(\displaystyle \frac{a+c}{a+c+b}<N\). Továbbá legyen \(\displaystyle k\) olyan pozitív egész, melyre \(\displaystyle s^k>N\), ilyen létezik, mert tudjuk, hogy \(\displaystyle a>c\), azaz \(\displaystyle s>1\). Most definiáljuk az \(\displaystyle f\) függvényt: legyen \(\displaystyle f(n)=\lceil s^{n+k} \rceil - N\). Világos, hogy ez tényleg a pozitív egészekbe képez, lássuk be, hogy ez teljesíti az egyenlőtlenségeinket is. Ehhez először érdemes megfigyelni, hogy

\(\displaystyle a+bs+cs^2=a-2a+a=0.\)

Ekkor

\(\displaystyle af(n)+bf(n+1)+cf(n+2)=a(\lceil s^{n+k} \rceil - N)+b(\lceil s^{n+k+1} \rceil - N)+c(\lceil s^{n+k+2} \rceil - N) \leq\)

\(\displaystyle \leq a(s^{n+k} +1- N)+b( s^{n+k+1} - N)+c( s^{n+k+2} +1 - N)=\)

\(\displaystyle =s^{n+k}(a+bs+cs^2)+(a+c)-(a+b+c)N=(a+c)-(a+b+c)N<0,\)

azaz \(\displaystyle f\) kielégíti a feladat feltételeit.

Már csak azt kell megmutatnunk, hogy ha \(\displaystyle b>-2\sqrt{ac}\), akkor nem létezik megfelelő függvény. Indirekten tegyük fel, hogy mégis létezik megfelelő \(\displaystyle f\) függvény, és legyen \(\displaystyle g(n)=\left(\frac{\sqrt{c}}{\sqrt{a}}\right)^nf(n)\), azaz \(\displaystyle f(n)=g(n)s^n\), valamint legyen \(\displaystyle b=-2\sqrt{ac}+\varepsilon\), ahol \(\displaystyle \varepsilon>0\). Írjuk be ezeket a függvényegyenletbe, és használjuk ki megint, amit korábban már egyszer megállapítottunk, hogy \(\displaystyle a=\sqrt{ac} \cdot s=cs^2\).

\(\displaystyle af(n)+bf(n+1)+cf(n+2)=ag(n)s^n+(\varepsilon-2\sqrt{ac})g(n+1)s^{n+1}+cg(n+2)s^{n+2}=\)

\(\displaystyle as^n(g(n)-2g(n+1)+g(n+2))+\varepsilon s^{n+1}g(n+1)<0.\)

Legyen \(\displaystyle h(n)=g(n+1)-g(n)\). Osztva \(\displaystyle as^n\)-nel, rendezve és \(\displaystyle h\)-t behelyettesítve azt kapjuk, hogy

\(\displaystyle h(n+1)<h(n)-\frac{\varepsilon s}{a}g(n+1).\)

Világos, hogy \(\displaystyle g\) pozitív értékeket vesz fel, így ebből azonnal látható, hogy a \(\displaystyle h(n)\) sorozat monoton csökken. Valami hasonlót szeretnénk csinálni, mint a 3.2.1 esetben, de ugyanaz nem működik kapásból, mert nem tudjuk, hogy a \(\displaystyle g\) és a \(\displaystyle h\) függvények egész értékeket vesznek fel. De szerencsére az \(\displaystyle \frac{\varepsilon s}{a}g(n+1)\) tag miatt mégis menni fog.

Ha létezik olyan \(\displaystyle k\), melyre \(\displaystyle h(k)<0\), akkor a monoton csökkenés miatt innentől minden \(\displaystyle l \geq k\) esetén \(\displaystyle h(l) \leq h(k)<0\), így \(\displaystyle g(l+1)-g(k)=\sum_{i=k}^l h(i) \leq (l-k+1)h(k)\). Elég nagy \(\displaystyle l\)-et választva a jobb oldal tetszőlegesen kicsit lehet, azaz elég nagy \(\displaystyle l\) esetén \(\displaystyle g(l+1)<0\), ami ellentmondás. Tehát elég lenne azt belátni, hogy létezik \(\displaystyle h(k)<0\). Tegyük fel, hogy nem létezik ilyen, ez éppen azt jelenti, hogy a \(\displaystyle g(n)\) sorozat monoton nő, azaz \(\displaystyle g(n+1) \geq g(1)\) minden \(\displaystyle n\)-re. Ám ekkor

\(\displaystyle h(n+1)<h(n)-\frac{\varepsilon s}{a}g(1),\)

ahol \(\displaystyle \frac{\varepsilon s}{a}g(1)\) egy pozitív konstans, így ekkor azt is tudjuk, hogy a \(\displaystyle h(n)\) sorozat minden lépésben legalább egy fix pozitív konstanssal csökken, így elég nagy \(\displaystyle k\)-ra negatívnak kell lennie, ami ellentmondás. Ezzel befejeztük a bizonyítást.

Statisztika:

Az A. 880. feladat értékelése még nem fejeződött be.

A KöMaL 2024. áprilisi matematika feladatai