ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 109671
Темы:    [ Объединение, пересечение и разность множеств ]
[ Мощность множества. Взаимно-однозначные отображения ]
Сложность: 4+
Классы: 8,9,10,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 элемент (в частности, n2k+1 ). Следовательно, объединение множеств A1, A2,..,An состоит не более чем из n+n(2k-n+1)=n(2k+2-n) элементов. Максимальное значение выражения n(2k+2-n) равно (k+1)2 . Но тогда, по условию задачи, все Ai должны иметь общий элемент. Противоречие.

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .