Az A. 852. feladat (2023. április)

A. 852. Legyenek $\displaystyle (a_i,b_i)$ páronként különböző számpárok, ahol $\displaystyle 1 \le i \le n$-re $\displaystyle a_i$ és $\displaystyle b_i$ pozitív egészek. Bizonyítsuk be, hogy

$\displaystyle (a_1+a_2+\ldots+a_n) (b_1+b_2+\ldots+b_n)>\frac{2}{9} n^3,$

és mutassuk meg, hogy az állítás éles, azaz bármilyen $\displaystyle c>\frac{2}{9}$ esetén lehetséges, hogy

$\displaystyle (a_1+a_2+\ldots+a_n) (b_1+b_2+\ldots+b_n)<cn^3.$

Javasolta: OKTV feladat alapján Pach Péter Pál (Budapest)

(7 pont)

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

1. megoldás: Először igazoljuk, hogy az egyenlőtlenség éles. Legyen $\displaystyle n=\frac{k(k+1)}{2}$ valamilyen $\displaystyle k$ pozitív egészre és legyenek az $\displaystyle (a_i,b_i)$ párok az összes olyan pár, melyekre $\displaystyle a_i+b_i \leq k+1$. Ekkor

$\displaystyle \sum_{i=1}^n a_i=\sum_{i=1}^k \sum_{b_j=i} a_j=\sum_{i=1}^k \binom{k+2-i}{2}=\binom{k+2}{3},$

ahol az első egyenlőségben egyszerűen $\displaystyle b_i$ értékei szerint rendeztük a szummát, ha $\displaystyle b_j=i$ akkor $\displaystyle a_j$ az $\displaystyle \{1,2, \ldots , k+1-i\}$ halmazból való, így csak ezeknek az összege $\displaystyle \binom{k+2-i}{2}$, és végül az utolsó egyenlőség az úgynevezett zokni azonosság, amit például $\displaystyle k$ szerinti indukcióval nagyon egyszerű bizonyítani.

Egy másik lehetőség a fentiek bizonyítására: a fenti számpárokra úgy is gondolhatunk, hogy egy $\displaystyle k+2$ hosszúságú pálcát három pozitív egész hosszúságú szakaszra bontunk (a három rész sorrendje számít), és ebből az első kettő hosszát vesszük $\displaystyle a_i$-nek és $\displaystyle b_i$-nek. Mivel $\displaystyle k+1$ helyen törhetjük el a pálcát, látható, hogy miért $\displaystyle \binom{k+1}{2}$ darab számpárunk van. Az összeg is egyszerű így: mivel mindhárom rész összege ugyanannyi, és összesen $\displaystyle (k+2)\binom{k+1}{2}$ a részek összege, így mindegyik összeg egyenlő $\displaystyle (k+2)\binom{k+1}{2}/3=\binom{k+2}{3}$-mal.

Szimmetria miatt $\displaystyle \sum_{i=1}^n b_i=\binom{k+2}{3}$ is teljesül, azaz

$\displaystyle \sum_{i=1}^n a_i \sum_{i=1}^n b_i \sim \frac{k^6}{36},$

ahol $\displaystyle \sim$ az aszimptotikus egyenlőséget jelöli, azaz a két oldal hányadosa 1-hez tart, ahogy $\displaystyle k \to \infty$. Ez azért igaz, mert a kiszámolt $\displaystyle \sum_{i=1}^n a_i$ és $\displaystyle \sum_{i=1}^n b_i$ értékek $\displaystyle k$-ban polinomok $\displaystyle \frac{k^3}{6}$ együtthatóval, és ismert, hogy a polinomok azimptotikusan a fő tagjukhoz tartanak. Ha $\displaystyle c$ tetszőleges pozitív konstans, akkor

$\displaystyle cn^3=c\left(\frac{k(k+1)}{2}\right)^3 \sim c \cdot \frac{k^6}{8}.$

Ezeket összevetve, mivel $\displaystyle \frac{k^6/36}{k^6/8}=\frac{2}{9}$, így tetszőleges $\displaystyle c \geq \frac{2}{9}$ esetén elég nagy $\displaystyle k$-ra teljesülni fog, hogy

$\displaystyle \left(a_1+a_2+\ldots+a_n\right)\left(b_1+b_2+\ldots+b_n\right)<c n^3,$

éppen ahogy akartuk, így tényleg éles ilyen szempontból az egyenlőtlenség. Most térjünk rá az egyenlőtlenség bizonyítására.

Előrebocsátunk néhány megállapítást a koordinátasíkon az $\displaystyle xy=c$ egyenlettel adott hiperbolákról (pontosabban az ilyen hiperboláknak a pozitív síknegyedbe eső ágáról), ahol $\displaystyle c$ pozitív konstans. Ezek mindegyike vagy magától értetődő, vagy pedig közvetlen számolással ellenőrizhető.

- A pozitív síknegyed valamely $\displaystyle (a,b)$ pontjára $\displaystyle ab>c$ akkor és csak akkor teljesül, ha a pont a hiperbola belsejében (azaz a görbe fölött) tartózkodik. Az $\displaystyle (a,b)$ pont akkor és csak akkor van a hiperbola belsejében, ha a hiperbolaág mindegyik érintőegyenese fölött van.

- Az $\displaystyle xy=c$ hiperbola egy $\displaystyle (p,q)$ pontjában az érintőegyenes egyenlete $\displaystyle qx+py=2pq$. A $\displaystyle (p,q)$ pont felezi ennek az egyenesnek a koordinátatengelyek közé eső szakaszát. Valamely $\displaystyle (a,b)$ pont akkor és csak akkor van az érintőegyenes fölött, ha a $\displaystyle qa+pb>2pq$ egyenlőtlenség teljesül.

A feladat állítását úgy is fogalmazhatjuk, hogy az $\displaystyle a=a_1+\ldots+a_n$, $\displaystyle b=b_1+\ldots+b_n$ formulákkal adott $\displaystyle (a,b)$ pont az $\displaystyle xy=(2/9)n^3$ hiperbola belsejében van.

Az állítást $\displaystyle n$ szerinti teljes indukcióval bizonyítjuk be. Az $\displaystyle n=1$ esetben az egyenlőtlenség nyilvánvaló. Tegyük fel, hogy $\displaystyle n\ge 2$ és $\displaystyle (n-1)$-re már bebizonyítottuk. Legyenek adottak a feladatbeli $\displaystyle a_i$, $\displaystyle b_i$ számok, $\displaystyle a=a_1+\ldots+a_n$, $\displaystyle b=b_1+\ldots+b_n$. A fentiek szerint azt kell ellenőrizni, hogy bármely olyan $\displaystyle p,q$ pozitív számokra, amelyekre $\displaystyle pq=(2/9)n^3$ fennáll, a $\displaystyle qa+pb>(4/9)n^3$ egyenlőtlenség is érvényes. Legyen tehát adott $\displaystyle p,q>0$, melyekre $\displaystyle pq=(2/9)n^3$.

Tekintsük azt a derékszögű háromszöget, amelyet a pozitív síknegyedből a $\displaystyle qx+py=(2/3)n^2$ egyenletű egyenes vág le. (Ez az egyenes párhuzamos a szóban forgó hiperbola $\displaystyle (p,q)$ pontbeli érintőjével.) Ennek a háromszögnek az $\displaystyle x$-tengelyen levő csúcsa az $\displaystyle x=(2/3)n^2/q$ pontban, az $\displaystyle y$-tengelyen levő csúcsa az $\displaystyle y=(2/3)n^2/p$ pontban van. Így a háromszög területe $\displaystyle (2/9)n^4/pq=n$-nel egyenlő. Ha a feladatban adott $\displaystyle (a_i,b_i)$ számpárok mindegyikéhez tekintjük azt az egységnyi oldalú rácsnégyzetet, amelynek $\displaystyle (a_i,b_i)$ a jobb felső csúcsa, akkor ezeknek a négyzeteknek az összterülete $\displaystyle n$, tehát nem lehetséges, hogy a háromszög mindegyiküket lefedje. Létezik tehát olyan $\displaystyle i_0$ index, hogy az $\displaystyle (a_{i_0},b_{i_0})$ pont a háromszögön kívül van, vagyis $\displaystyle qa_{i_0}+pb_{i_0}>(2/3)n^2$.

Az $\displaystyle (a_{i_0},b_{i_0})$ számpárt elhagyjuk az adottak közül, és a maradék $\displaystyle (n-1)$ számpárra fogjuk alkalmazni az indukciós feltevést. Legyen

$\displaystyle a'=\sum_{i\ne i_0}a_i,\quad b'=\sum_{i\ne i_0}b_i,\quad p'=p\sqrt{\left (\frac{n-1}{n}\right )^3},\quad q'=q\sqrt{\left (\frac{n-1}{n}\right )^3}.$

Be kell látnunk a $\displaystyle qa+pb>(4/9)n^3$ egyenlőtlenséget. A $\displaystyle pq=(2/9)n^3$ feltételből $\displaystyle p'$ és $\displaystyle q'$ definíciója szerint $\displaystyle p'q'=(2/9)(n-1)^3$ következik. Az indukciós feltevés szerint az $\displaystyle (a',b')$ pont az $\displaystyle xy=(2/9)(n-1)^3$ hiperbola belsejében van. Ezt úgy használjuk ki, hogy ennek a hiperbolának a $\displaystyle (p',q')$ pontbeli érintőjét tekintjük. Az $\displaystyle (a',b')$ pont efölött az érintő fölött van, azaz $\displaystyle q'a'+p'b'>(4/9)(n-1)^3$. Ezt felhasználva

$\displaystyle qa+pb = q(a'+a_{i_0})+p(b'+b_{i_0})=(qa'+pb')+(qa_{i_0}+pb_{i_0})=$

$\displaystyle = \sqrt{\left (\frac{n}{n-1}\right )^3}(q'a'+p'b')\, +\, (qa_{i_0}+pb_{i_0})>$

$\displaystyle > \frac{4}{9}\sqrt{\left (\frac{n}{n-1}\right )^3}(n-1)^3\, +\, \frac{2}{3}n^2=$

$\displaystyle = \frac{4}{9}\left (\sqrt{\big ((n-1)n\big )^3}\, +\,\frac{3}{2}n^2\right ).$

Ahhoz, hogy a kívánt $\displaystyle qa+pb>(4/9)n^3$ egyenlőtlenséget megkapjuk, elég belátni, hogy $\displaystyle \sqrt{\big ((n-1)n\big )^3}\, +\,(3/2)n^2\,\ge\, n^3$. Ez átrendezéssel és négyzetre emeléssel közvetlenül ellenőrizhető (kihasználva azt is, hogy $\displaystyle n\ge 2$).

2. megoldás: Az élességre nem mutatunk új bizonyítást, csak az egyenlőtlenségre. Jelölje $\displaystyle c_j$ azoknak a pároknak a számát, ahol $\displaystyle a_i=j$, és legyen $\displaystyle k$ a legnagyobb egész, amire $\displaystyle c_j\ne 0$. Az egyenlőtlenség bal oldalán álló összeg nyilván csökken, ha bármelyik tényező bármelyik tagját csökkentjük, és ezért feltehető, hogy azoknál a pároknál, ahol $\displaystyle a_i=j$, a megfelelő $\displaystyle b_i$-k az $\displaystyle 1,2,\ldots, c_j$ értékeket futják be. (Hasonló gondolatmenettel az is látszik, hogy $\displaystyle c_1,\ldots,c_k$ egyike sem nulla, továbbá hogy a $\displaystyle c_j$ sorozat monoton fogyó, de ezt nem fogjuk használni.)

Ekkor tehát $\displaystyle n=c_1+c_2+\ldots +c_k$, továbbá $\displaystyle a_1+\ldots+a_n=c_1+2c_2+\ldots+kc_k$, végül $\displaystyle b_1+\ldots+b_n = (c_1^2+c_1+c_2^2+c_2+\ldots+c_k^2+c_k)/2$.

Vegyük észre, hogy a $\displaystyle c_1^2+c_1+c_2^2+c_2+\ldots+c_k^2+c_k$ összeg csökken, ha elhagyjuk a $\displaystyle c_1,\ldots,c_k$ tagokat. Legyen $\displaystyle x_i=c_i/n$, ezek összege $\displaystyle 1$. Az állítás nyilván igaz $\displaystyle k=1$ esetén, elég tehát a következőt bizonyítani.

Tétel: Rögzített $\displaystyle k\ge 2$ mellett legyenek $\displaystyle x_1,x_2,\ldots, x_k$ nemnegatív valós számok, melyekre $\displaystyle x_1+\ldots+x_k=1$. Ekkor

$\displaystyle (x_1+2x_2+\ldots+ kx_k)(x_1^2+\ldots+x_k^2)\ge C_k=(2/9)\frac{2k^2+k-1-\sqrt{2k+2}}{k^2-k}\,,$

és egyenlőség abban az egyetlen esetben áll, amikor $\displaystyle 1\le i\le k$ esetén

$\displaystyle x_i= \frac{2(k+1)(k-i)+(2i-k-1)\sqrt{2k+2}}{k^3-k}\,.$

A $\displaystyle C_k$ számok szigorúan fogyó sorozatot alkotnak, amely felülről $\displaystyle 4/9$-hez tart.

A $\displaystyle C_k$ sorozat fogyó, mert $\displaystyle k\ge 2$ esetén

$\displaystyle (k^3-k)(C_k-C_{k+1}) = 3k+1 + (k-1)\sqrt{2k+4}-(k+1)\sqrt{2k+2}>0\,,$

hiszen $\displaystyle 2\big(\sqrt{2k+4}-\sqrt{2k+2}\big)=4/\big(\sqrt{2k+4}+\sqrt{2k+2}\big)<1$. A határértéke nyilván $\displaystyle 4/9$, ha $\displaystyle k\to\infty$. (A fogyás onnan is látható, hogy $\displaystyle k$-t növelve csak nőnek a lehetőségeink az új változók érkezésével, így a minimum csökkenni fog.)

Vezessük be a $\displaystyle P(x_2,\ldots, x_k)=x_1+2x_2+\ldots+ kx_k=1+x_2+2x_3+\ldots+ (k-1)x_k$, $\displaystyle S(x_2,\ldots,x_k)=x_1^2+\ldots+x_k^2=(1-x_2-\ldots-x_k)^2+x_2^2+\ldots+x_k^2$ jelöléseket, legyen $\displaystyle f(x_2,\ldots, x_k)=P(x_2,\ldots, x_k)S(x_2,\ldots, x_k)$, végül $\displaystyle H$ álljon azokból az $\displaystyle (x_2,\ldots,x_k)$ sorozatokból, melyekre $\displaystyle x_2\ge 0,\ldots, x_k\ge 0$ és $\displaystyle x_2+\ldots+x_k\le 1$. Fel fogjuk használni a következő állítást analízisből.

Állítás: A $\displaystyle H$ halmazon értelmezett $\displaystyle f$ folytonos függvény felveszi a minimumát alkalmas $\displaystyle x_2=d_2,\ldots, x_k=d_k$ helyen. Legyen $\displaystyle f_i(t)=f(d_2,\ldots,d_{i-1},t,d_{i+1},\ldots,d_k)$. Ekkor minden $\displaystyle i$-re teljesül, hogy vagy az $\displaystyle f_i$ függvény értelmezve van a $\displaystyle d_i$ pont egy környezetében, és ott a deriváltja nulla, vagy a minimumhely az értelmezési tartomány határán van, amikor a $\displaystyle d_i=0$ vagy $\displaystyle d_2+\ldots+d_k=1$.

Nevezzük belső pontnak azokat az $\displaystyle (x_2,\ldots,x_k)$ pontokat, ahol $\displaystyle 0<x_2,\ldots,x_k$ és $\displaystyle x_2+\dots+x_k<1$, a többit határpontnak. Azt, hogy $\displaystyle f(x_2,\ldots,x_k)\ge C_k$, kerülő úton mutatjuk meg, a következőképpen. Tudjuk, hogy $\displaystyle f$ a $\displaystyle H$ halmazon valahol (akár több helyen) felveszi a (globális) minimumát. Ezek közül a belső pontokban mindegyik $\displaystyle f_i'$ értéke nulla. Kiderül, hogy egyetlen olyan $\displaystyle (d_2,\ldots,d_k)$ belső pont van, ahol $\displaystyle f_i'(d_i)=0$ minden $\displaystyle i$-re, és ebben a pontban $\displaystyle f$ értéke $\displaystyle C_k$. Másfelől viszont megmutatjuk $\displaystyle k$ szerinti indukcióval, hogy a $\displaystyle H$ határpontjaiban $\displaystyle f$ értéke legalább $\displaystyle C_{k-1}>C_k$. Ebből már következik, hogy a határon nincs globális minimumhely. Ezért csak egyetlen globális minimumhely van, nevezetesen $\displaystyle (d_2,\ldots,d_k)$, és mivel itt a függvényérték $\displaystyle C_k$, ezért tényleg igaz, hogy $\displaystyle f(x_2,\ldots,x_k)> C_k$ a $\displaystyle H$ minden $\displaystyle (x_2,\ldots,x_k)\ne (d_2,\ldots d_k)$ elemére.

Ha $\displaystyle k=2$, akkor $\displaystyle f(x)=(1+x)\big((1-x)^2+x^2\big)=2x^3-x+1$. Két határpont van, $\displaystyle x=0$ és $\displaystyle x=1$, ezekben a függvény értéke $\displaystyle 1$. A derivált $\displaystyle 6x^2-1$, ennek gyökei $\displaystyle \pm 1/\sqrt{6}$. A $\displaystyle [0,1]$ intervallumban globális minimum van az $\displaystyle x=d_2=1/\sqrt{6}$ helyen, az itt felvett függvényérték könnyen ellenőrizhetően $\displaystyle C_2<1$.

Először a tartomány határán lévő pontokat vizsgáljuk meg, $\displaystyle k$ szerinti indukciót alkalmazunk. Ha $\displaystyle x_2+\ldots+x_k=1$, akkor az első zárójelből 1-et elhagyva a szorzat csökken, viszont $\displaystyle \big(x_2+2x_3+\ldots+(k-1)x_k\big)(x_2^2+\ldots+x_k^2)\ge C_{k-1}$ az indukciós feltevés szerint. Ha pedig $\displaystyle x_i=0$, akkor ismét az első zárójelbeli összeget csökkenthetjük így:

$\displaystyle 1+x_2+2x_3+\ldots +(i-2)x_{i-1}+(i-1)x_{i+1} +\ldots+(k-2)x_k\,,$

tehát az indukciós feltevés miatt ismét a $\displaystyle C_{k-1}$ alsó becslést kapjuk. Vagyis $\displaystyle H$ határán a $\displaystyle C_{k-1}$ alsó becslés érvényes, most meg kell határoznunk azokat a belső pontokat, ahol mindegyik $\displaystyle f_i'$ értéke nulla. Legyen $\displaystyle (d_2,\ldots,d_k)$ egy ilyen pont.

Legyen $\displaystyle P_i(t)=P(d_2,\ldots,d_{i-1},t,d_{i+1},\ldots,d_k)$ és $\displaystyle P=P_i(d_i)$ (ez nyilván minden $\displaystyle i$-re ugyanaz a szám), továbbá $\displaystyle S_i(t)=S(d_2,\ldots,d_{i-1},t,d_{i+1},\ldots,d_k)$ és $\displaystyle S=S_i(d_i)$. Hasonló szellemben legyen $\displaystyle X_i(t)=1-d_2-d_3-\ldots -d_{i-1}-t-d_{i+1}-\ldots -d_k$. Végül legyen $\displaystyle d_1=1-d_2-\ldots-d_k=X_i(d_i)$.

Az $\displaystyle f_i$ függvény $\displaystyle t$-nek harmadfokú polinomja. Deriváljuk az $\displaystyle f_i(t)=P_i(t)S_i(t)$ függvényt. Nyilván $\displaystyle P_i'(t)=(i-1)$ és

$\displaystyle S_i'(t) = X_i^2(t)'+(t^2)'= 2X_i(t)X_i'(t) + 2t =2\big(t-X_i(t)\big)\,.$

Így a Leibniz-szabály szerint

$\displaystyle f_i'(t)=P_i'(t)S_i(t) + P_i(t)S_i'(t)= (i-1)S_i(t) + 2P_i(t)\big(t-X_i(t)\big)\,.$

Ezért $\displaystyle t$ helyére $\displaystyle d_i$-t helyettesítve

$\displaystyle 0=f_i'(d_i)=(i-1)S + 2P(d_i-d_1)\quad (2\le i\le k)\,.$

Innen $\displaystyle d_i=d_1-(i-1)d$, ahol $\displaystyle d=S/(2P)>0$, vagyis a $\displaystyle d_i$ számok fogyó számtani sorozatot alkotnak. Az egyenleteket összeadva, és a $\displaystyle d_1+\ldots+d_k=1$ összefüggést felhasználva $\displaystyle d_1=(1/k)+d(k-1)/2$ adódik.

Meghatározzuk $\displaystyle d$ értékét a $\displaystyle d=S/(2P)$ összefüggésből. Használjuk a következő rövidítéseket: $\displaystyle k_1=(k^2+k)/2$ és $\displaystyle k_2 = 1^2+2^2+\ldots+ k^2 = k(k+1)(2k+1)/6$. Ekkor $\displaystyle d_i=d_1-(i-1)d$ miatt

Ezt a $\displaystyle d=S/(2P)$ és $\displaystyle d_1=(1/k)+d(k-1)/2$ összefüggésekkel kombinálva a

$\displaystyle \big((k^3-k)/4\big) d^2 -(k+1)d+1/k=0$

másodfokú egyenletet kapjuk $\displaystyle d$-re. A megoldások

$\displaystyle d=\frac{2(k+1\pm\sqrt{2k+2})}{k^3-k}\,, \qquad d_1=\frac{2k\pm\sqrt{2k+2}}{k^2+k}\,.$

Ekkor

$\displaystyle d_k=d_1-(k-1)d=\frac{\pm \sqrt{2k + 2}}{k^2 + k}\,.$

Mivel $\displaystyle d_k\ge 0$, csak az a $\displaystyle d$ érték jön szóba, ahol a négyzetgyök előtt $\displaystyle -$ jel van. Ekkor $\displaystyle k\ge 2$ esetén

$\displaystyle P=(1/6)(2k+\sqrt{2k+2}+2)\quad \text{és}\quad S=(2/3)(2k-\sqrt{2k+2})/(k^2-k)\,,$

ahonnan a bizonyítandó egyenlőtlenség bal oldala

$\displaystyle PS= (2/9)\frac{2k^2+k-1-\sqrt{2k+2}}{k^2-k}=C_k\,.$

Statisztika:

5 dolgozat érkezett.
6 pontot kapott:	Varga Boldizsár.
5 pontot kapott:	1 versenyző.
4 pontot kapott:	2 versenyző.
2 pontot kapott:	1 versenyző.

A KöMaL 2023. áprilisi matematika feladatai