Задачка про множество

[JS]

В n-элементном множестве E (n>2) выделено m различных собственных подмножеств. Известно, что для любых двух различных элементов из E существует единственное из выделенных подмножеств такое, что в нём содержатся оба этих элемента. Доказать, что $m\geqslant n$

[Хорхе]

[:\/\/\/\/\/:]

[нг]

Хорхе
Как Вас следует понимать? На решение Ваш текст не тянет…

[RIP]

Хорхе
Раздел же не называется "Новые олимпиадные задачи". Я, например, эту задачу не знал.

Пусть $E=\{e_1,\ldots,e_n\}$, и $E_1,\ldots,E_m$ - выбранные подмножества.
Рассмотрим матрицу $A$ размера $n\times m$:

$$a_{ij}=\begin{cases}1,&e_i\in E_j;\\0,&e_i\notin E_j.\end{cases}$$

Обозначим $B=AA^T$. Тогда при $i\ne j\quad b_{ij}=1$ (это означает, что найдётся ровно одно подмножество $E_k$, содержащее оба елемента $e_i,e_j$).
Далее, для любого $i\quad b_{ii}\geqslant2$. Действительно, это означает, что элемент $e_i$ содержится по крайней мере в двух подмножествах $E_k$. Почему это так? Берём любое $j\ne i$. Найдётся $E_{k_1}\supset\{e_i;e_j\}$. Возьмём любой $e_l\notin E_{k_1}$. Тогда найдётся $E_{k_2}\supset\{e_i;e_l\}$.
Но тогда матрица $B$ (строго) положительно определённая, т.к. для любого $x=(x_1,\ldots,x_n)\in\mathbb{R}^n\setminus\{0\}$ имеем
$(Bx,x)=(x_1+\ldots+x_n)^2+(b_{11}-1)x_1^2+\ldots+(b_{nn}-1)x_n^2>0$.
В частности, матрица $B$ невырождена, т.е. имеет ранг $n$. Поскольку $B=AA^T$, то $n=rkB\leqslant rkA\leqslant m$.