KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

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 11 April 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 solution.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley