2014 dxdy logo

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

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




 
 Максимизация числа сочетаний
Сообщение10.09.2013, 20:17 
Есть множество A состоящее из n элементов, пронумерованных от 1 до n. $n \geqslant 2$
Список - непустой набор элементов из множества A, при этом никакой элемент не содержится дважды в списке.
Любые два списка $B_i$ и $B_j$ $(i \ne j)$ должны удовлетворять сразу двум условиям:
$B_i$ \bigcap B_j \ne B_i$
$B_i$ \bigcap B_j \ne B_j$

Иными словами, у $B_i$ должен быть элемент, которого нет у $B_j$, и наоборот, у $B_j$ должен быть элемент, которого нет у $B_i$.
Необходимо максимизировать количество списков.
Подскажите, как доказать или опровергнуть, что нельзя сделать списков больше, чем $C_n^{\lfloor \frac{n}{2} \rfloor}$

 
 
 
 Re: Максимизация числа сочетаний
Сообщение10.09.2013, 21:17 
Аватара пользователя
Это теорема Шпернера.

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group