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