 |
Az A. 869. feladat (2024. január) |
A. 869. Legyenek A és B adott valós számok. A 0≤x1≤x2≤⋯≤xn valós számok összege A, a 0≤y1≤y2≤⋯≤yn valós számok összege B.
Mi n∑i=1(xi−yi)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 A vagy B negatív, a feladatnak nincs értelme, tehát tegyük fel, hogy A,B≥0.
Belátjuk, hogy (max 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
|
|