Условие
Часть подмножеств некоторого конечного множества выделена.
Каждое выделенное подмножество состоит в точности из
2
k элементов
(
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} , то
в каждом из них останется
2
k-n+1
элемент (в частности,
n2
k+1
). Следовательно, объединение множеств
A1,
A2,..,An состоит не более чем из
n+n(2
k-n+1)
=n(2
k+2
-n)
элементов. Максимальное значение выражения
n(2
k+2
-n)
равно
(
k+1)
2 . Но тогда, по условию задачи, все
Ai должны иметь
общий элемент. Противоречие.
Источники и прецеденты использования
|
олимпиада |
Название |
Всероссийская олимпиада по математике |
год |
Год |
1998 |
Этап |
Вариант |
5 |
Класс |
Класс |
10 |
задача |
Номер |
98.5.10.4 |