Требуется доказать, что для всех $%k > 2^{n-1}$% не существует множества подмножеств множества $%\{1,2,\dots,n\}$% мощности $%k$%, такого что любые два множества из него пересекаются по непустому множеству (т.е. пересечение двух любых непусто). Построил пример такого множества размера $%k=2^{n-1}$%, а как доказать, что больших нет? задан 8 Окт '19 16:24 greedoid_ |
@greedoid_: смысл вопроса непонятен. Множество всех подмножеств множества {1,2,...,n} имеет мощность 2^n. Тогда его и возьмём. Оно будет иметь мощность k=2^n, что больше 2^{n-1}.
Здесь какая-то явная ошибка в формулировке.
@falcao да, конечно, исправил формулировку
@greedoid_: тогда доказательство такое. Все 2^n подмножеств разбиваем на пары (X,X') из подмножества и его дополнения. В каждой паре пересечение пусто, и в набор из k подмножеств попадает не более одного. Отсюда k<=2^{n-1}.