Problem B. 4351. (March 2011)
B. 4351. Some subsets containing at least two elements of an n-element set are selected. Given that any two elements of the set occur together exactly once in some selected subset, prove that the number of the subsets selected is either 1 or at least n.
(5 pont)
Deadline expired on April 11, 2011.
Sorry, the solution is available only in Hungarian. Google translation
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.
Statistics:
9 students sent a solution. 5 points: Perjési Gábor, Sieben Bertilla. 4 points: Hartvig 147 Dániel. 3 points: 3 students. 2 points: 1 student. 0 point: 1 student. Unfair, not evaluated: 1 solutions.
Problems in Mathematics of KöMaL, March 2011