Problem B. 4951. (April 2018)

B. 4951. The elements of a set \(\displaystyle V\) are \(\displaystyle n\)-dimensional vectors (ordered \(\displaystyle n\)-tuples of numbers) of which each coordinate is \(\displaystyle -1\), \(\displaystyle 0\) or \(\displaystyle 1\). No three different vectors of \(\displaystyle V\) add up to the zero vector. Show that \(\displaystyle |V|\le 2\cdot 3^{n-1}\).

(4 pont)

Deadline expired on May 10, 2018.

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

Megoldás. Ha \(\displaystyle \mathbf{v}\) egy olyan vektor, melynek mindegyik koordinátája \(\displaystyle -1,0\), vagy \(\displaystyle 1\), akkor \(\displaystyle \mathbf{v'}\) legyen az a vektor, melyet úgy kapunk \(\displaystyle \mathbf{v}\)-ből, hogy koordinátái közül minden \(\displaystyle -1\)-et \(\displaystyle 0\)-ra, minden \(\displaystyle 0\)-t \(\displaystyle 1\)-re, minden \(\displaystyle 1\)-et \(\displaystyle -1\)-re változtatunk (egyszerre). Tehát például \(\displaystyle \mathbf{v}=(1,1,0,-1,1)\) esetén \(\displaystyle \mathbf{v'}=(-1,-1,1,0,-1)\).

Legyen most \(\displaystyle \mathbf{v}\in \{-1,0,1\}^n\) tetszőleges, és tekintsük a \(\displaystyle \mathbf{v},~\mathbf{v'},~\mathbf{v''}\) vektorokat. Bármely \(\displaystyle 1\leq i\leq n\) esetén teljesül, hogy \(\displaystyle v_i,v'_i,v''_i\) valamilyen sorrendben \(\displaystyle -1,~0\) és \(\displaystyle 1\), vagyis \(\displaystyle v_i+v_i'+v_i''=(-1)+0+1=0\). Tehát \(\displaystyle \mathbf{v}+\mathbf{v'}+\mathbf{v''}=\mathbf{0}\), vagyis \(\displaystyle V\) a \(\displaystyle \mathbf{v},~\mathbf{v'},~\mathbf{v''}\) vektorok közül legfeljebb kettőt tartalmazhat.

Mivel \(\displaystyle \mathbf{v'''}=\mathbf{v}\), ezért két különböző \(\displaystyle \mathbf{u},~\mathbf{v}\in \{-1,0,1\}^n\) vektor esetén a \(\displaystyle \{\mathbf{v},\mathbf{v'},\mathbf{v''}\}\) és \(\displaystyle \{\mathbf{u},\mathbf{u'},\mathbf{u''}\}\) hármasok vagy megegyeznek, vagy diszjunktak. így a \(\displaystyle \{-1,0,1\}^n\) halmazt összesen \(\displaystyle 3^{n-1}\) darab \(\displaystyle \{\mathbf{v},\mathbf{v'},\mathbf{v''}\}\) hármasba oszthatjuk, \(\displaystyle V\) minden ilyen hármasból legfeljebb 2 vektort tartalmazhat, így \(\displaystyle |V|\leq 2\cdot 3^{n-1}\).

Megjegyzés. \(\displaystyle |V|=2\cdot 3^{n-1}\) előfordulhat: tartalmazza \(\displaystyle V\) azokat a \(\displaystyle \{-1,0,1\}^n\)-beli vektorokat, melyek első koordinátája nem 0. Ekkor három \(\displaystyle V\)-beli vektor összegének első koordinátája biztosan páratlan (\(\displaystyle -3,-1,1\) vagy \(\displaystyle 3\)), és így nem a nullvektor, ugyanakkor \(\displaystyle |V|=2\cdot 3^{n-1}\).

Statistics:

68 students sent a solution.
4 points:	Apagyi Dávid, Argay Zsolt, Beke Csongor, Biczó Benedek, Bukva Dávid, Busa 423 Máté, Csaplár Viktor, Csiszár Zoltán, Dobák Dániel, Döbröntei Dávid Bence, Fleiner Zsigmond, Fraknói Ádám, Fülöp Anna Tácia, Füredi Erik Benjámin, Gáspár Attila, Geretovszky Anna, Győrffi Ádám György, Győrffy Ágoston, Győrffy Johanna, Hegedűs Dániel, Hervay Bence, Jánosik Áron, Janzer Orsolya Lili, Kántor András Imre, Kerekes Anna, Kitschner Bernadett, Kocsis Anett, Kószó Máté József, Kupás Vendel Péter, Mikulás Zsófia, Nagy Dorottya, Nagy Nándor, Noszály Áron, Póta Balázs, Schifferer András, Schrettner Jakab, Sebestyén Pál Botond, Shuborno Das, Soós 314 Máté, Szabó 417 Dávid, Szabó 864 Blanka, Szabó 991 Kornél, Szabó 997 Balázs István, Terjék András József, Tiderenczl Dániel, Tóth Ábel, Várkonyi Zsombor, Velich Nóra, Weisz Máté, Zsigri Bálint.
3 points:	4 students.
2 points:	2 students.
1 point:	7 students.
0 point:	5 students.

Problems in Mathematics of KöMaL, April 2018