A B. 4351. feladat (2011. március)

B. 4351. Egy n elemű halmaznak kiválasztottuk néhány, legalább kételemű részhalmazát. Tudjuk, hogy a halmaz bármely két eleme pontosan egyszer szerepel együtt egy kiválasztott részhalmazban. Igazoljuk, hogy a kiválasztott részhalmazok száma vagy 1, vagy legalább n.

(5 pont)

A beküldési határidő 2011. április 11-én LEJÁRT.

Megoldás. A halmaz elemei legyenek \(\displaystyle p_1,\ldots,p_n\), a kiválasztott részhalmazok \(\displaystyle H_1,\ldots,H_m\). Ha valamelyik \(\displaystyle p_i\) csak egyetlen részhalmazban szerepel, akkor a feltételek szerint abban a halmazban az összes elemnek szerepelnie kell, további részhalmaz pedig nem lehet kiválasztva, vagyis ekkor \(\displaystyle m=1\). Tegyük fel tehát, hogy minden \(\displaystyle p_i\) legalább két \(\displaystyle H_j\)-ben szerepel. Minden \(\displaystyle p_i\) elemhez rendeljünk hozzá egy \(\displaystyle m\) tagú \(\displaystyle {\bf v}_i\) számsorozatot, amelynek \(\displaystyle j\)-edik tagja 1, ha \(\displaystyle p_i\in H_j\), egyébként pedig 0. Feltevésünk szerint mindegyik számsorozatban legalább 2 darab 1-es szerepel. Ha \(\displaystyle {\bf x}=(x_1,\ldots,x_m)\) és \(\displaystyle {\bf y}=(y_1,\ldots,y_m)\) két \(\displaystyle m\)-tagú valós számsorozat, \(\displaystyle \alpha\) pedig tetszőleges valós szám, akkor legyen

\(\displaystyle {\bf x}+{\bf y}=(x_1+y_1,\ldots,x_m+y_m),\ \alpha{\bf x}=(\alpha x_1,\ldots,\alpha x_m),\ \langle {\bf x},{\bf y}\rangle=x_1y_1+\ldots+x_my_m.\)

Feltevésünk szerint minden \(\displaystyle i\)-re \(\displaystyle \langle {\bf v}_i,{\bf v}_i\rangle\ge 2\), a feladat feltétele szerint pedig \(\displaystyle i\ne j\) esetén \(\displaystyle \langle {\bf v}_i,{\bf v}_j\rangle=1\). A bevezetett műveletekre az összeadás kommutativitásán és asszociativitásán túl érvényesek az alábbi azonosságok is:

\(\displaystyle \langle {\bf x},{\bf y}\rangle=\langle {\bf y},{\bf x}\rangle,\ \langle \alpha{\bf x},{\bf y}\rangle=\alpha\langle {\bf x},{\bf y}\rangle,\ \langle {\bf x}+{\bf y},{\bf z}\rangle= \langle {\bf x},{\bf z}\rangle+\langle {\bf y},{\bf z}\rangle.\)

Ezek alapján, ha az \(\displaystyle \alpha_1,\ldots,\alpha_n\) valós számokra \(\displaystyle \alpha_1{\bf v}_1+\ldots+\alpha_n{\bf v}_n={\bf 0}=(0,\ldots,0)\), akkor

\(\displaystyle 0=\langle{\bf 0},{\bf 0}\rangle= \langle \sum_{i=1}^n\alpha_i{\bf v}_i,\sum_{i=1}^n\alpha_i{\bf v}_i \rangle=\sum_{i=1}^n\alpha_i^2\langle{\bf v}_i,{\bf v}_i\rangle+ 2\sum_{1\le i<j\le n}\alpha_i \alpha_j \langle{\bf v}_i,{\bf v}_j\rangle=\)

\(\displaystyle =\sum_{i=1}^n\alpha_i^2\left(\langle{\bf v}_i,{\bf v}_i\rangle-1\right) +\left( \sum_{i=1}^n\alpha_i\right)^2,\)

ami csak úgy teljesülhet, ha \(\displaystyle \alpha_1=\ldots=\alpha_n=0\). Az \(\displaystyle \alpha_1{\bf v}_1+\ldots+\alpha_n{\bf v}_n={\bf 0}\) feltétel tagonként egy-egy lineáris egyenletet jelent az \(\displaystyle \alpha_1,\ldots,\alpha_n\) ismeretlenekre nézve. Ennek az \(\displaystyle m\) darab egyenletből álló egyenletrendszernek (ahol az egyenlőség jobb oldalán mindig 0 áll) a fentiek szerint csak egyetlen megoldása van, mégpedig \(\displaystyle \alpha_1=\ldots=\alpha_n=0\). Ez viszont csak úgy lehetséges, ha \(\displaystyle m\ge n\). Valóban, ha \(\displaystyle m<n\) lenne, vagyis az egyenletek száma kisebb lenne az ismeretlenek számánál, akkor az egyenletrendszernek végtelen sok megoldása lenne. Ekkor ugyanis így okoskodhatnánk: ha \(\displaystyle \alpha_n\) minden egyenletben 0 együtthatóval szerepel, akkor értékét tetszőlegesen megválaszthatjuk. Ha valamelyik egyenletben nem 0 az együtthatója, akkor abból az egyenletből \(\displaystyle \alpha_n\) kifejezhető a többi ismeretlen segítségével. Ezt a többi egyenletbe beírva kapunk egy \(\displaystyle m-1\) egyenletből álló, \(\displaystyle n-1\) ismeretlent tartalmazó lineáris egyenletrendszert, ahol az egyenlőségek jobb oldalán ismétcsak 0 áll. Ezt ismételgetve végül az egyenletrendszert egyetlen egyenletre redukálhatjuk, amelyben legalább két ismeretlen szerepel; ennek viszont nyilván végtelen sok megoldása van.

Statisztika:

9 dolgozat érkezett.
5 pontot kapott:	Perjési Gábor, Sieben Bertilla.
4 pontot kapott:	Hartvig 147 Dániel.
3 pontot kapott:	3 versenyző.
2 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.
Nem versenyszerű:	1 dolgozat.

A KöMaL 2011. márciusi matematika feladatai