Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

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