Олимпиадная задача по теории множеств для 8–11 класса от Дольникова В.Л.
Задача
Часть подмножеств некоторого конечного множества выделена. Каждое выделенное подмножество состоит в точности из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 должны иметь
общий элемент. Противоречие.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь