A B. 4927. feladat (2018. január)

B. 4927. Legyen \(\displaystyle A\) és \(\displaystyle B\) vektorok egy-egy véges halmaza, továbbá legyen \(\displaystyle A+B=\{\mathbf{v} +\mathbf{w} \mid \mathbf{v}\in A\), \(\displaystyle \mathbf{w} \in B\}\). Mutassuk meg, hogy \(\displaystyle |A+B|\ge |A|+|B|-1\).

(5 pont)

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

Megoldás. Válasszuk a koordinátarendszert úgy, hogy az \(\displaystyle A\)-beli vektorok \(\displaystyle x\)-koordinátái páronként különbözőek legyenek, s ugyanez fennálljon a \(\displaystyle B\)-beli vektorokra is. Ez pontosan akkor teljesül, ha az \(\displaystyle x\)-tengely nem merőleges a \(\displaystyle \mathbf v -\mathbf w\) alakú vektorok egyikére sem, ahol vagy \(\displaystyle \mathbf v, \mathbf w\in A\) vagy \(\displaystyle \mathbf v, \mathbf w\in B\). Vagyis az \(\displaystyle x\)-tengely véges sok vektorra nem lehet merőleges, ami nyilvánvalóan elérhető.

Feltehető, hogy az \(\displaystyle A\)-beli \(\displaystyle \mathbf{a_1}, \mathbf{a_2}, \ldots , \mathbf{a_k}\) vektorok \(\displaystyle x\)-koordinátáira \(\displaystyle a_1<a_2<\ldots<a_k\) teljesül, és hasonlóan a \(\displaystyle B\)-beli \(\displaystyle \mathbf{b_1}, \mathbf{b_2}, \ldots , \mathbf{b_m}\) vektorok \(\displaystyle x\)-koordinátáira \(\displaystyle b_1<b_2<\ldots<b_m\). Ekkor \(\displaystyle a_1+b_1<a_1+b_2<\ldots<a_1+b_m<a_2+b_m<a_3+b_m<\ldots<a_k+b_m\) éppen \(\displaystyle k+m-1\) darab páronként különböző szám. Ebből következik, hogy a megfelelő \(\displaystyle \mathbf{a_1}+\mathbf{b_1},\) \(\displaystyle \mathbf{a_1}+\mathbf{b_2}, \ldots, \mathbf{a_1}+\mathbf{b_m},\) \(\displaystyle \mathbf{a_2}+\mathbf{b_m},\) \(\displaystyle \mathbf{a_3}+\mathbf{b_m}, \ldots, \mathbf{a_k}+\mathbf{b_m}\) vektorok is páronként különböznek. Így \(\displaystyle |A+B|\ge k+m-1=|A|+|B|-1\), amit bizonyítani akartunk.

Az egyenlőtlenség éles: ha a vektorok illeszkednek az \(\displaystyle x\)-tengelyre, továbbá minden lehetséges \(\displaystyle i\) és \(\displaystyle j\) esetén \(\displaystyle a_i=i\) és \(\displaystyle b_j=j\), akkor könnyű látni, hogy \(\displaystyle |A+B|=|A|+|B|-1\).

Megjegyzés. Sajnos a szövegezésből kimaradt, hogy a probléma térben vagy síkban értendő, de mint a fenti megoldás mutatja, ez a feladat nehézségét és megoldását nem befolyásolja.

Statisztika:

54 dolgozat érkezett.
5 pontot kapott:	Beke Csongor, Busa 423 Máté, Csertán András, Csiszár Zoltán, Daróczi Sándor, Dobák Dániel, Döbröntei Dávid Bence, Fleiner Zsigmond, Fuisz Gábor, Fülöp Anna Tácia, Füredi Erik Benjámin, Gáspár Attila, Győrffi Ádám György, Győrffy Ágoston, Janzer Orsolya Lili, Kerekes Anna, Kiss Gergely, Kupás Vendel Péter, Markó Anna Erzsébet, Molnár Bálint, Molnár-Sáska Zoltán, Nagy Nándor, Noszály Áron, Pituk Gábor, Saár Patrik, Schifferer András, Schrettner Jakab, Schweitzer Ádám, Sebestyén Pál Botond, Szabó 417 Dávid, Szabó 864 Blanka, Szabó 991 Kornél, Szabó 997 Balázs István, Tiszay Ádám, Tóth 827 Balázs, Tubak Dániel, Vári-Kakas Andor, Várkonyi Zsombor, Weisz Máté, Zólomy Kristóf, Zsigri Bálint.
4 pontot kapott:	Fraknói Ádám, Póta Balázs.
3 pontot kapott:	2 versenyző.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	7 versenyző.

A KöMaL 2018. januári matematika feladatai