Az A. 869. feladat (2024. január)

A. 869. Legyenek \(\displaystyle A\) és \(\displaystyle B\) adott valós számok. A \(\displaystyle 0\le x_1\le x_2\le\dots\le x_n\) valós számok összege \(\displaystyle A\), a \(\displaystyle 0\le y_1\le y_2\le\dots\le y_n\) valós számok összege \(\displaystyle B\).

Mi \(\displaystyle {\sum_{i=1}^n (x_i-y_i)^2}\) lehetséges legnagyobb értéke?

Javasolta: Csikvári Péter (Budapest)

(7 pont)

A beküldési határidő 2024. február 12-én LEJÁRT.

Ha \(\displaystyle A\) vagy \(\displaystyle B\) negatív, a feladatnak nincs értelme, tehát tegyük fel, hogy \(\displaystyle A,B \ge 0\).

Belátjuk, hogy \(\displaystyle (\max(A,B))^2-\frac{2AB}{n}+\frac{(\min(A,B))^2}{n}\) a válasz, ami \(\displaystyle A\geq{B}\)-re elérhető \(\displaystyle x_1=\dots=x_{n-1}=0\), \(\displaystyle x_n=A\) és \(\displaystyle y_1=\dots=y_n=\frac{B}{n}\) számokkal, míg \(\displaystyle A<B\)-re \(\displaystyle x_1=\dots=x_n=\frac{A}{n}\) és \(\displaystyle y_1=\dots=y_{n-1}=0\), \(\displaystyle y_n=B\) számokkal.

A megoldás alapgondolata a következő: a megadott feltételeket kielégítő \(\displaystyle (x_1,\ldots,x_n)\) pontok az \(\displaystyle n\)-dimenziós térnek egy \(\displaystyle n-1\) dimenziós alterében (,,síkjában'') egy \(\displaystyle n\)-csúcsú testet fognak alkotni. Például ha \(\displaystyle n=3\) és \(\displaystyle A=2\), akkor egy háromszöget kapunk a három dimenziós térben, melynek csúcsai \(\displaystyle (2/3,2/3,2/3)\), \(\displaystyle (0,1,1)\) és \(\displaystyle (0,0,2)\). A feladat pedig azt kérdezi, hogy két ilyen test lehető legtávolabb lévő pontjai milyen messze vannak egymástól.

A fenti gondolat a következő módon tehető formálissá: bármely megengedett \(\displaystyle (x_1, x_2, \ldots, x_n)\)-re \(\displaystyle (x_1, x_2, \ldots, x_n)\) előáll a \(\displaystyle \alpha_1(\frac{A}{n}, \ldots, \frac{A}{n})+\alpha_2(0,\frac{A}{n-1},\ldots,\frac{A}{n-1})+...+\alpha_{n-1}(0, \ldots, 0, \frac{A}{2},\frac{A}{2})+\alpha_n(0,\ldots, 0, A)\) alakban, ahol \(\displaystyle A\alpha_1=nx_1\) és \(\displaystyle A\alpha_i=(n+1-i)(x_i-x_{i-1})\), ha \(\displaystyle 2\le i \le n\). Ekkor \(\displaystyle A(\alpha_1+\alpha_2+\dots+\alpha_n)=x_1+x_2+\dots+x_n=A\), azaz \(\displaystyle \alpha_1+\alpha_2+\dots+\alpha_n=1\), és minden \(\displaystyle \alpha_j\) nemnegatív valós szám (\(\displaystyle 1\leq{j}\leq{n}\)).

Nevezzük az \(\displaystyle (0, 0, \ldots 0, \frac{A}{k}, \frac{A}{k}, \ldots, \frac{A}{k})\) vektort \(\displaystyle v_k\)-nak, és ennek a \(\displaystyle j\)-edik koordinátáját \(\displaystyle v_{k,j}\)-nek. Ezekkel a jelölésekkel tehát az \(\displaystyle (x_1, x_2, \ldots, x_n)\) vektort felírtuk \(\displaystyle \sum_{k=1}^n \alpha_k v_k\) alakban, ahol minden \(\displaystyle \alpha_k\ge 0\), és \(\displaystyle \sum_{k=1}^n \alpha_k=1\). Ez a precíz lineáris algebrai megfogalmazása annak, hogy a keresett pontok az \(\displaystyle n\) darab \(\displaystyle (0,...,0,A)\), \(\displaystyle (0,...,0,\frac{A}{2},\frac{A}{2})\),..., \(\displaystyle (\frac{A}{n},...,\frac{A}{n})\) pont konvex burkát alkotják. Most megfogalmazzuk és bebizonyítjuk azt a szemléletes tényt, hogy két poliéder legtávolabbi pontja két csúcs lesz:

Lemma: Mindig létezik olyan \(\displaystyle 1\le k\le n\), amelyre \(\displaystyle \sum_{j=1}^n (x_j-y_j)^2\le \sum_{j=1}^n (v_{k,j}-y_j)^2\).

Lássunk egy precíz algebrai bizonyítást a lemmára:

A súlyozott számtani-négyzetes közepek közötti egyenlőtlenségből következik, hogy minden \(\displaystyle 1\le j\le n\) koordinátára teljesül, hogy

\(\displaystyle \sum_{k=1}^n \alpha_k (v_{k,j}-y_j)^2\ge \sum_{k=1}^n \big(\alpha_k(v_{k,j}-y_j)\big)^2=(x_j-y_j)^2.\)

Ezt összeadva az összes koordinátára azt kapjuk, hogy

\(\displaystyle \sum_{k=1}^n \alpha_k \sum_{j=1}^n (v_{k,j}-y_j)^2=\sum_{j=1}^{n} \sum_{k=1}^n \alpha_k (v_{k,j}-y_j)^2\ge \sum_{j=1}^{n} (x_j-y_j)^2.\)

Mivel az \(\displaystyle \alpha_k\) súlyok mind nemnegatívak, és összegük \(\displaystyle 1\), ebből az következik, hogy

\(\displaystyle \max_{k} \sum_{j=1}^n (v_{k,j}-y_j)^2\ge \sum_{j=1}^{n} (x_j-y_j)^2,\)

tehát létezik olyan \(\displaystyle k\), amelyre \(\displaystyle (x_1, x_2, \ldots, x_n)\) vektort lecserélve \(\displaystyle v_k=( 0, 0, \ldots 0, \frac{A}{k}, \frac{A}{k}, \ldots, \frac{A}{k})\)-ra nem csökken \(\displaystyle \sum_{j=1}^{n} (x_j-y_j)^2\) értéke.

—

Ezután, hogy \(\displaystyle (x_1, x_2, \ldots, x_n)\) értékét beállítottuk egy \(\displaystyle v_k\) vektornak, szintén a lemma alapján beállíthatjuk \(\displaystyle (y_1, y_2, \ldots, y_n)\) értékét is egy \(\displaystyle v'_r\) vektornak úgy, hogy továbbra sem csökken \(\displaystyle \sum_{j=1}^{n} (x_j-y_j)^2\) értéke (ahol a fentiekhez hasonlóan \(\displaystyle v'_r=(0,...0,\frac{B}{r},...,\frac{B}{r}\)).

Ezzel tehát azt kaptuk, hogy létezik \(\displaystyle e\) és \(\displaystyle f\), amire \(\displaystyle \sum_{j=1}^n (x_j-y_j)^2\le \sum_{j=1}^n (v_{e,j}-v'_{f,j})^2\).

Ha \(\displaystyle e>f\), akkor

\(\displaystyle \sum_{j=1}^n (v_{e,j}-v_{f,j})^2=f(\frac{A}{e}-\frac{B}{f})^2+(e-f)(\frac{A}{e}-0)^2+(n-e)0^2=\frac{A^2}{e}-\frac{2AB}{e}+\frac{B^2}{f}.\)

Általánosan tehát

\(\displaystyle \sum_{j=1}^n (v_{e,j}-v_{f,j})^2=\frac{A^2}{e}+\frac{B^2}{f}-\frac{2AB}{max(e,f)}.\)

Az általánosság rovása nélkül tegyük fel, hogy \(\displaystyle A\ge B\), ekkor a rendezési tétel szerint

\(\displaystyle \frac{A^2}{e}+\frac{B^2}{f}-\frac{2AB}{\max(e,f)}\le \frac{A^2}{\min(e,f)}+\frac{B^2}{\max(e,f)}-\frac{2AB}{\max(e,f)}.\)

Értelemszerűen

\(\displaystyle \frac{A^2}{\min(e,f)}+\frac{B^2}{\max(e,f)}-\frac{2AB}{\max(e,f)}\le \frac{A^2}{1}+\frac{B^2}{\max(e,f)}-\frac{2AB}{\max(e,f)},\)

és \(\displaystyle 0\le B\le A\), így \(\displaystyle (B-2A)B\le 0\), tehát

\(\displaystyle \frac{A^2}{1}+\frac{B^2}{\max(e,f)}-\frac{2AB}{\max(e,f)}\le A^2+\frac{B^2}{n}-\frac{2AB}{n},\)

így általánosan megkaptuk, hogy

\(\displaystyle \sum_{j=1}^n (x_j-y_j)^2\le (\max(A,B))^2-\frac{2AB}{n}+\frac{(\min(A,B))^2}{n}\)

mindig teljesül, ez az érték pedig elérhető a megoldás elején bemutatott módon.

Statisztika:

15 dolgozat érkezett.
7 pontot kapott:	Bodor Mátyás, Czanik Pál, Duchon Márton, Fleischman Illés, Foris Dávid, Tarján Bernát, Tianyue DAI, Varga Boldizsár, Wiener Anna.
5 pontot kapott:	1 versenyző.
3 pontot kapott:	2 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.
Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt:	1 dolgozat.

A KöMaL 2024. januári matematika feladatai