|
Требуется доказать, что для всех $%k > 2^{n-1}$% не существует множества подмножеств множества $%\{1,2,\dots,n\}$% мощности $%k$%, такого что любые два множества из него пересекаются по непустому множеству (т.е. пересечение двух любых непусто). Построил пример такого множества размера $%k=2^{n-1}$%, а как доказать, что больших нет? задан 8 Окт 16:24 
greedoid_ |
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
8 Окт 16:24
показан
36 раз
обновлен
8 Окт 17:41
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
@greedoid_: смысл вопроса непонятен. Множество всех подмножеств множества {1,2,...,n} имеет мощность 2^n. Тогда его и возьмём. Оно будет иметь мощность k=2^n, что больше 2^{n-1}.
Здесь какая-то явная ошибка в формулировке.
@falcao да, конечно, исправил формулировку
@greedoid_: тогда доказательство такое. Все 2^n подмножеств разбиваем на пары (X,X') из подмножества и его дополнения. В каждой паре пересечение пусто, и в набор из k подмножеств попадает не более одного. Отсюда k<=2^{n-1}.