Problem B. 4927. (January 2018)

B. 4927. Let \(\displaystyle A\) and \(\displaystyle B\) be finite sets of vectors, and let \(\displaystyle A+B=\{\mathbf{v}+\mathbf{w} \mid \mathbf{v}\in A\), \(\displaystyle \mathbf{w} \in B\}\). Show that \(\displaystyle |A+B|\ge|A|+|B|-1\).

(5 pont)

Deadline expired on February 12, 2018.

Sorry, the solution is available only in Hungarian. Google translation

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.

Statistics:

54 students sent a solution.
5 points:	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 points:	Fraknói Ádám, Póta Balázs.
3 points:	2 students.
2 points:	1 student.
1 point:	1 student.
0 point:	7 students.

Problems in Mathematics of KöMaL, January 2018