Банк задач по математике

Задача 5.1.1

Докажите, что в любом семействе попарно пересекающихся подмножеств $n$ -элементного множества не более $2^{n-1}$ подмножеств.

?

Задача 5.1.2

(1)(2)

Пусть $2 \leqslant t \leqslant n-2$ .

?

(1)

Постройте семейство из $2^{n-t}$ подмножеств $n$ -элементного множества, любые два из которых пересекаются не менее чем по $t$ элементам.

(2)

Существует ли такое семейство из $2^{n-t}+1$ подмножеств?

Задача 5.1.3

(1)(2)

Пусть $\mathscr {F}$ — любое семейство $k$ -элементных подмножеств $n$ -элементного множества.

?

(1)

Если $2k \leqslant n$ и любые два подмножества из $\mathscr {F}$ пересекаются, то $\left|\mathscr {F}\right| \leqslant \binom {n-1}{k-1}$ .

(2)

Если $2k \geqslant n$ и объединение никаких двух подмножеств из $\mathscr {F}$ не есть всё $n$ -элементное множество, то $\left|\mathscr {F}\right| \leqslant \binom {n-1}{k}$ .

Задача 5.1.4

Любое семейство из двадцати 5-элементных подмножеств 15-элементного множества можно так разбить на 6 подсемейств, чтобы любые два непересекающихся подмножества лежали в разных подсемействах.

?

Примечание.

?

В таких ситуациях (см. п. 7.1) обычно вместо разбиения на подсемейства говорят о раскраске в разные цвета. Тогда вопреки наглядному представлению о раскраске красятся множества, но при этом не красятся их элементы.

Задача 5.1.5

(1)(2)(3)(4)

Для $l < k$ обозначим через $M(n,k,l)$ минимальное количество таких $k$ -элементных подмножеств множества $\mathscr {R}_{n}$ , что любое $l$ -элементное подмножество множества $\mathscr {R}_{n}$ целиком содержится хотя бы в одном из них. Например, задача 1.6.2 (1) утверждает, что $M(n,k,l) \geqslant \binom {n}{l} / \binom {k}{l}$ .

?

(1)

Найдите $M(n,k,1)$ .

(2)

Найдите $M(6k+3,3,2)$ .

(3)

Найдите $M(n,3,2)$ .

(4)

Докажите, что $M(n,k,l) \geqslant nM(n-1,k-1,l-1)/k$ .

Пересечения подмножеств