Az A. 712. feladat (2017. december)

A. 712. Egy pozitív valós számokból álló szigorúan monoton növekvő \(\displaystyle a_1,a_2,\dots\) sorozatot törpének nevezünk, ha tetszőleges \(\displaystyle c>0\)-hoz megadható \(\displaystyle N\), melyre \(\displaystyle a_n<cn\) áll fenn \(\displaystyle n=N,N+1,\dots\) esetén. Továbbá azt mondjuk, hogy \(\displaystyle a_n\) sipka, ha \(\displaystyle {1\le i\le n-1}\) esetén \(\displaystyle a_{n-i}+a_{n+i}<2a_n\).

Igaz-e, hogy minden törpe sorozatnak végtelen sok sipkája van?

(5 pont)

A beküldési határidő 2018. január 10-én LEJÁRT.

Megoldásvázlat. Egy kép többet ér ezer szónál:

Megoldás. Legyen még \(\displaystyle a_0=0\). Legyen \(\displaystyle i_0=0\), majd pedig minden \(\displaystyle k\)-ra \(\displaystyle i_{k+1}\) legyen a legnagyobb olyan \(\displaystyle i_k\)-nál nagyobb index, melyre

\(\displaystyle \frac{a_{i_{k+1}}-a_{i_k}}{i_{k+1}-i_k}=\max_{i>i_k}\frac{a_i-a_{i_k}}{i-i_k}=:\lambda_k.\)

Belátjuk, hogy ha \(\displaystyle i_k\) létezik, akkor \(\displaystyle i_{k+1}\) is létezik. Figyeljük ugyanis meg, hogy valamilyen \(\displaystyle c>0\)-val nem teljesülhet végtelen sok \(\displaystyle i\) indexre \(\displaystyle \frac{a_i-a_{i_k}}{i-i_k}\ge c\), hiszen akkor ezek közül az elég nagy \(\displaystyle i\) értékekre \(\displaystyle a_i\ge (c/2)i\) teljesül, ami ellentmond a törpe-feltételnek. Ez azt jelenti, hogy a jobb oldalon álló maximum létezik (hisz \(\displaystyle \frac{a_i-a_{i_k}}{i-i_k}\) mindig pozitív a szigorú monoton növekedés okán), és a maximális érték véges sok \(\displaystyle i\) indexre fordul elő, vagyis \(\displaystyle i_{k+1}\) létezik.

Ábrázoljuk derékszögű koordináta-rendszerben az \(\displaystyle (n,a_n)\) pontokat \(\displaystyle (n=0,1,2,\dots)\). Minden \(\displaystyle k=0,1,\dots\)-ra legyen

\(\displaystyle g_k(x)=a_{i_k}+\lambda_k (x-i_k)\)

az a lineáris függvény, amely az \(\displaystyle (i_k,a_{i_k})\) és \(\displaystyle (i_{k+1},a_{i_{k+1}})\) pontokra illeszthető.

1. állítás. \(\displaystyle k\ge 0\)-ra \(\displaystyle \lambda_k>\lambda_{k+1}\).

Bizonyítás. \(\displaystyle a_{i_{k+1}}\) definíciójából adódóan

\(\displaystyle \frac{a_{i_{k+2}}-a_{i_k}}{i_{k+2}-i_k}<\frac{a_{i_{k+1}}-a_{i_k}}{i_{k+1}-i_k},\)

amit átalakítva:

\(\displaystyle \frac{\lambda_{k+1}(i_{k+2}-i_{k+1})+\lambda_k(i_{k+1}-i_k)}{i_{k+2}-i_k}<\lambda_k,\)

\(\displaystyle \lambda_{k+1}\frac{i_{k+2}-i_{k+1}}{i_{k+2}-i_k}<\lambda_k\left(1-\frac{i_{k+1}-i_k}{i_{k+2}-i_k}\right),\)

amit átosztva éppen \(\displaystyle \lambda_{k+1}<\lambda_k\) adódik. \(\displaystyle \blacksquare\)

2. állítás. Ha \(\displaystyle n\ge i_k\), akkor \(\displaystyle a_n\le g_k(n)\).

Bizonyítás. Az \(\displaystyle i_{k+1}\) definíciója szerint

\(\displaystyle \frac{a_n-a_{i_k}}{n-i_k}\le \lambda_k,\)

\(\displaystyle a_n\le a_{i_k}+\lambda_k(n-i_k)=f(n),\)

ahogy kívántuk. \(\displaystyle \blacksquare\)

3. állítás. Ha \(\displaystyle k<\ell\), akkor \(\displaystyle 0\le x<i_{k+1}\) esetén \(\displaystyle g_k(x)<g_\ell(x)\).

Bizonyítás. Előbb belátjuk az állítást minden \(\displaystyle \ell\)-re a \(\displaystyle k=\ell-1\) speciális esetben. Az 1. állítás szerint \(\displaystyle \lambda_{\ell-1}>\lambda_\ell\), s így \(\displaystyle 0\le x<i_\ell\) esetén

\(\displaystyle g_{\ell-1}(x)=a_{i_{\ell-1}}+\lambda_{\ell-1} (x-i_{\ell-1})=a_{i_\ell}+\lambda_{\ell-1}(x-i_\ell)<a_{i_\ell}+\lambda_\ell (x-i_\ell)=g_\ell(x).\)

Az állítás a speciális esetből indukcióval következik: \(\displaystyle 0\le x<i_{k+1}\) esetén

\(\displaystyle g_k(x)<g_{k+1}(x)<g_{k+2}(x)<\dots<g_\ell(x).\quad \blacksquare\)

Végül belátjuk, hogy \(\displaystyle a_{i_k}\) mindig sipka lesz. Legyen \(\displaystyle 1\le j\le i_{k}-1\). Ekkor ha \(\displaystyle i_t\le i_k-j<i_{t+1}\), akkor a 2., majd 3. állítást alkalmazva

\(\displaystyle a_{i_k-j}\le g_t(i_k-j)<g_k(i_k-j).\)

Tehát a 2. állítással becsülve \(\displaystyle a_{i_k+j}\)-t, \(\displaystyle g_k\) linearitása miatt

\(\displaystyle a_{i_k-j}+a_{i_k+j}<g_k(i_k-j)+g_k(i_k+j)=2g_k(i_k)=2a_{i_k}.\)

Ezzel beláttuk, hogy bármely törpe sorozatnak végtelen sok sipkája van.

Statisztika:

9 dolgozat érkezett.
5 pontot kapott:	Daróczi Sándor, Gáspár Attila, Imolay András, Janzer Orsolya Lili, Matolcsi Dávid, Schrettner Jakab, Schweitzer Ádám, Szabó Kristóf.
4 pontot kapott:	Bukva Balázs.

A KöMaL 2017. decemberi matematika feladatai