2014-06-08
В множестве, состоящем из $n \geq 5$ элементов, выбрано $n + 1$ различных трехэлементных подмножеств. Доказать, что найдутся два выбранных подмножества, имеющих ровно один общий элемент.
Решение:
Предположим противное. Тогда любые два из выбранных подмножеств либо не пересекаются, либо имеют ровно два общих элемента. Если подмножества А и В имеют ровно два общих элемента, то будем писать $A \sim B$. Пусть $A, B, C$ - три подмножества. Докажем, что если $A \sim B$ и $B \sim C$, то $A \sim C$. Действительно, пусть $A = \{a; b; c\}, B = \{a; b; d \}$. Так как множество $C$ должно иметь с множеством $B$ два общих элемента, среди которых обязательно есть $a$ или $b$, то $C$ пересекается с $A$, а значит, $C \sim A$. Таким образом, все выбранные подмножества разбиваются на классы, в каждом из которых любые два разных множества имеют ровно два общих элемента, а множества из разных классов не пересекаются. Для каждого клаcca множеств возможны 3 случая:
1) класс охватывает ровно 3 элемента;
2) класс охватывает ровно 4 элемента;
3) класс охватывает больше 4 элементов.
В первом случае класс состоит ровно из одного множества, во втором – количество множеств не больше четырех (так как у множества из 4 элементов существует всего 4 различных трехэлементных подмножества). Рассмотрим третий случай. Пусть выбраны два множества из рассматриваемого класса: $A = \{ a; b; c\}$ и $B = \{ a; b; d \}$. Существует элемент $e$, отличный от $a, b, c, d$ и принадлежащий некоторому множеству $C$ из этого класса. Из условий $A \sim C$ и $B \sim C$ получаем, что $C = \{ a; b; e \}$. Поэтому и любое множество $D$ из этого класса в силу условий $A \sim D, B \sim D, C \sim D$ содержит элементы $a$ и $b$, Тогда количество множеств в классе ровно на 2 меньше количества элементов в этом классе (каждому элементу, отличному от $a, b$, соответствует ровно одно множество, которому он принадлежит). Таким образом, в каждом классе количество множеств не больше количества элементов. Однако общее количество множеств больше общего количества элементов. Противоречие.