Экстремальная задача о множествах

[artfin]

Добрый день!
Помогите решить задачку.

Множество U содержит 2n элементов. В нем выделено k подмножеств, причем ни одно из них не является подмножеством другого. Каково может быть максимальное значение k?

Основной вопрос заключается в том, как доказать, что все подмножества должны быть одинаковой мощности?
Методов решения таких задач я не знаю, поэтому я попытался через вероятность попадания элемента в подмножества, но как то уперся...Видимо это как то можно сделать, но я не знаю как.

Отделено откуда-то из подразделов. //АКМ

[Sonic86]

artfin в сообщении #491856 писал(а):

Множество U содержит 2n элементов. В нем выделено k подмножеств, причем ни одно из них не является подмножеством другого. Каково может быть максимальное значение k?

Если взять все множества мощности $n$ - получим $\binom{2n}{n}$ множеств. Эта система множеств будет максимальной (недополняемой с сохранением искомого свойства).

artfin в сообщении #491856 писал(а):

Основной вопрос заключается в том, как доказать, что все подмножества должны быть одинаковой мощности?
Методов решения таких задач я не знаю, поэтому я попытался через вероятность попадания элемента в подмножества, но как то уперся...Видимо это как то можно сделать, но я не знаю как.

Можно попробовать так: пусть $S$ - произвольная система, в которой ни одно из подмножеств не является подмножеством другого. Пусть $m$ - минимальная из мощностей множества $S$ и этой мощностью обладают множества $M_1,...,M_k$. Рассмотрим все варианты добавлений элементов из $U$ к каждому из $M_j$ - получим новые множества $M_1',...,M_s'$. Если выбросить из $S$ множества $M_1,...,M_k$ и добавить $M_1',...,M_s'$ и удалить дубли, получим новую систему $S'$. Верно ли, что в $S'$ ни одно из подмножеств не является подмножеством другого? Как соотносятся между собой $|S|$ и $|S'|$? Попробуйте также аналогично рассмотреть случай максимальной мощности с последующим отщеплением одного элемента. Какие выводы можно сделать?