Задача 109671

Темы:    [ Объединение, пересечение и разность множеств ] [ Мощность множества. Взаимно-однозначные отображения ]

Сложность: 4+ Классы: 8,9,10,11

Условие

Автор: Дольников В.Л.

Часть подмножеств некоторого конечного множества выделена. Каждое выделенное подмножество состоит в точности из 2k элементов ( k – фиксированное натуральное число). Известно, что в каждом подмножестве, состоящем не более чем из (k+1)² элементов, либо не содержится ни одного выделенного подмножества, либо все в нем содержащиеся выделенные подмножества имеют общий элемент. Докажите, что все выделенные подмножества имеют общий элемент.

Решение

Предположим противное. Тогда найдется такое n ( n>1 ), что любой набор из n-1 выделенного подмножества имеет общий элемент и существует n выделенных подмножеств A₁, A₂,..,A_n , не имеющих общего элемента. Исключим из набора A₁, A₂,..,A_n множество A_i . Оставшиеся имеют общий элемент, который мы обозначим через x_i . Заметим, что x_i x_j при i j . Каждое из множеств A_i содержит все элементы множества {x₁, x₂,..,x_n} , кроме x_i , поэтому, если из множеств A_i исключить элементы множества {x₁, x₂,..,x_n} , то в каждом из них останется 2k-n+1 элемент (в частности, n2k+1 ). Следовательно, объединение множеств A₁, A₂,..,A_n состоит не более чем из n+n(2k-n+1)=n(2k+2-n) элементов. Максимальное значение выражения n(2k+2-n) равно (k+1)² . Но тогда, по условию задачи, все A_i должны иметь общий элемент. Противоречие.

Источники и прецеденты использования

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	1998
Этап
Вариант	5
Класс
Класс	10
задача
Номер	98.5.10.4