|
|
 |
Условие
Часть подмножеств некоторого конечного множества выделена.
Каждое выделенное подмножество состоит в точности из 2k элементов
( k – фиксированное натуральное число). Известно, что в каждом
подмножестве, состоящем не более чем из (k+1)2 элементов,
либо не содержится ни одного выделенного подмножества, либо все
в нем содержащиеся выделенные подмножества имеют общий элемент.
Докажите, что все выделенные подмножества имеют общий элемент.
Решение
Предположим противное. Тогда найдется такое n ( n>1 ), что любой
набор из n-1 выделенного подмножества имеет общий элемент и
существует n выделенных подмножеств A1, A2,..,An , не имеющих общего
элемента. Исключим из набора A1, A2,..,An множество Ai .
Оставшиеся имеют общий элемент, который мы обозначим через xi .
Заметим, что xi xj при i
j . Каждое из множеств Ai содержит
все элементы множества {x1, x2,..,xn} , кроме xi , поэтому, если
из множеств Ai исключить элементы множества {x1, x2,..,xn} , то
в каждом из них останется 2k-n+1 элемент (в частности,
n
2k+1 ). Следовательно, объединение множеств A1,
A2,..,An состоит не более чем из n+n(2k-n+1)=n(2k+2-n)
элементов. Максимальное значение выражения n(2k+2-n) равно
(k+1)2 . Но тогда, по условию задачи, все Ai должны иметь
общий элемент. Противоречие.
