Feladat:	B.4951	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Noszály Áron ,  Schifferer András
Füzet:	2019/január, 26 - 27. oldal		PDF  |  MathML
Témakör(ök):	Feladat, Részhalmazok, Kombinatorikai leszámolási problémák, Vektorok lineáris kombinációi
Hivatkozás(ok):	Feladatok: 2018/április: B.4951

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   I. megoldás. Nevezzük bandának ($n$-dimenziós, $-1$, 0, 1 számokból álló) vektorok egy olyan háromelemű halmazát, amelyben a három vektor összege 0. Legyen $\oplus$ az a tetszőleges $n$ és $m$ dimenziójú $a$ és $b$ vektorokra értelmezett művelet, amelynek eredménye az az $n+m$ dimenziójú vektor, amelynek első $n$ koordinátája megegyezik $a$ koordinátáival, a további koordinátái pedig $b$ koordinátáival. Az $n$ szerinti indukcióval megmutatjuk, hogy az összes $n$-dimenziós (0, $\pm 1$ elemű) vektorok halmaza $3^{n-1}$ darab, páronként diszjunkt banda egyesítése. Az $n=1$ esetén ez nyilvánvalóan igaz: egyetlen banda van, a $\left\{-\mathrm{1,0,1}\right\}$. Tegyük föl, hogy $n=k$-ra igaz az állítás. Az $n=k+1$-re belátandó tekintsünk egy, az $n=k$ esethez tartozó felosztásban szereplő $\left\{A\mathrm{,}B\mathrm{,}C\right\}$ bandát; ebből a következő, $n=k+1$ dimenziós bandákat hozzuk létre: $\begin{array}{c}{\displaystyle \left\{A\oplus \mathrm{0,}B\oplus \mathrm{1,}C\oplus -1\right\}\mathrm{,}\left\{A\oplus -\mathrm{1,}B\oplus \mathrm{0,}C\oplus 1\right\}\mathrm{,}\left\{A\oplus \mathrm{1,}B\oplus -\mathrm{1,}C\oplus 0\right\}\mathrm{.}}\end{array}$ Ezzel (az indukciós feltevés alapján) $3\cdot 3^{k-1}=3^k$ darab $k+1$ dimenziós bandát konstruáltunk, amelyek páronként diszjunktak, így összesen $3\cdot 3^k=3^{k+1}$ darab különböző vektort tartalmaznak, tehát az összeset. A feladat állítása ebből már egyszerűen következik, hiszen a követelmény szerint minden bandából legfeljebb két vektort választhatunk, és a bandák száma $3^{n-1}$. A bizonyított becslés éles: ha az összes olyan vektort tekintjük, aminek az első koordinátája 1 vagy $-1$, a többi pedig (0, 1 és $-1$ közül választva) tetszőleges, akkor ezek száma éppen $2\cdot 3^{n-1}$, és semelyik háromnak az összege nem nulla.    Noszály Áron (Debrecen, Fazekas Mihály Gimn., 10. évf.)     II. megoldás. Az I. megoldásban bandáknak nevezett hármas csoportokba sorolást egyszerűbben is kaphatunk a következő módon. Mindegyik ($n$ dimenziós, a 0, 1, $-1$ elemekből képzett) vektorhoz adjuk hozzá a csupa 1-esből álló ($n$ dimenziós) $\text{e}$ vektort, a koordináták összeadását modulo 3 végezve. (Vagyis $0+1=1$, $-1+1=0$, $1+1=-1$ szerint.) Ezzel páronként diszjunkt, $\left\{\text{v}\mathrm{,}\text{v}+\text{e}\mathrm{,}\text{v}-\text{e}\right\}$ típusú vektor-hármasokhoz jutunk, amelyek elemei a bennük levő bármelyik vektorból az $\text{e}$ legfeljebb kétszeri hozzáadásával előállíthatók, a három vektor összege pedig $\text{v}+\left(\text{v}+\text{e}\right)+\left(\text{v}-\text{e}\right)=3\text{v}=\text{0}$.    Schifferer András (Kaposvár, Táncsics Mihály Gimn., 12. évf.)