Требуется доказать, что для всех $%k > 2^{n-1}$% не существует множества подмножеств множества $%\{1,2,\dots,n\}$% мощности $%k$%, такого что любые два множества из него пересекаются по непустому множеству (т.е. пересечение двух любых непусто).

Построил пример такого множества размера $%k=2^{n-1}$%, а как доказать, что больших нет?

задан 8 Окт 16:24

изменен 8 Окт 16:59

1

@greedoid_: смысл вопроса непонятен. Множество всех подмножеств множества {1,2,...,n} имеет мощность 2^n. Тогда его и возьмём. Оно будет иметь мощность k=2^n, что больше 2^{n-1}.

Здесь какая-то явная ошибка в формулировке.

(8 Окт 16:42) falcao

@falcao да, конечно, исправил формулировку

(8 Окт 16:59) greedoid_
1

@greedoid_: тогда доказательство такое. Все 2^n подмножеств разбиваем на пары (X,X') из подмножества и его дополнения. В каждой паре пересечение пусто, и в набор из k подмножеств попадает не более одного. Отсюда k<=2^{n-1}.

(8 Окт 17:41) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×559
×60

задан
8 Окт 16:24

показан
36 раз

обновлен
8 Окт 17:41

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru