2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Задачка про множество
Сообщение27.02.2007, 21:13 


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

 Профиль  
                  
 
 
Сообщение27.02.2007, 21:37 
Заслуженный участник
Аватара пользователя


14/02/07
2648
[:\/\/\/\/\/:]

 Профиль  
                  
 
 
Сообщение27.02.2007, 23:44 
Экс-модератор
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение28.02.2007, 04:08 
Заслуженный участник
Аватара пользователя


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

Пусть $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$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group