Задача 79483

Темы:    [ Объединение, пересечение и разность множеств ] [ Задачи с ограничениями ] [ Принцип Дирихле (прочее) ]

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

Условие

Даны 1985 множеств, каждое из которых состоит из 45 элементов, причём объединение любых двух множеств содержит ровно 89 элементов.
Сколько элементов содержит объединение всех этих 1985 множеств?

Решение

По условию каждые два множества пересекаются по одному элементу. Докажем, что все множества пересекаются по одному элементу. Предположим противное. Возьмём множество M₁. В нем найдётся элемент A, который принадлежит по крайней мере еще 45 множествам –  M₂, M₃, ..., M₄₆  (в противном случае общее число множеств не превосходило бы  44·45 + 1 = 1981).  По предположению, имеется множество, не содержащее элемента A. Оно пересекается по одному элементу с множествами  M₁, M₂, ..., M₄₆  и поэтому содержит 46, а не 45 элементов. Противоречие.

Ответ

44·1985 + 1 = 87341  элементов.

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	48
Год	1985
вариант
Класс	10
задача
Номер	4