A B. 4951. feladat (2018. április)

B. 4951. A \(\displaystyle V\) halmaz elemei olyan \(\displaystyle n\)-dimenziós vektorok (rendezett szám \(\displaystyle n\)-esek), amelyek minden koordinátája \(\displaystyle -1\), \(\displaystyle 0\) vagy \(\displaystyle 1\). Semelyik három különböző \(\displaystyle V\)-beli vektor összege nem a nullvektor. Mutassuk meg, hogy \(\displaystyle |V|\le 2\cdot 3^{n-1}\).

(4 pont)

A beküldési határidő 2018. május 10-én LEJÁRT.

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}\).

Statisztika:

68 dolgozat érkezett.
4 pontot kapott:	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 pontot kapott:	4 versenyző.
2 pontot kapott:	2 versenyző.
1 pontot kapott:	7 versenyző.
0 pontot kapott:	5 versenyző.

A KöMaL 2018. áprilisi matematika feladatai