Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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

$$\begin{gather*} P=\sum_{i=1}^k id_i = k_1d_1 - (k_2-k_1)d \\ S=\sum_{i=1}^k d_i^2 = kd_1^2 - 2(k_1-k)d_1d + (k_2-k^2)d^2\,. \end{gather*}$$

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