2014-06-08
Множество X состоит из $n$ элементов. Какое наибольшее число трехэлементных подмножеств можно выбрать в X так, чтобы любые два из них имели ровно один общий элемент?
Решение:
Обозначим искомое число через $k_{n}$. Предположим, что в множестве X выбраны $k_{n}$ трехэлементных подмножеств, любые два из которых имеют ровно один общий элемент. Возможны три случая.
а) Никакой элемент множества X не входит более чем в два трехэлементных множества. Пусть одно из множеств есть $\{ a; b; c \}$. Тогда любое из оставшихся множеств пересекается с множеством $\{ a; b; c \}$, причем среди этих оставшихся множеств не более одного множества содержит элемент а, не более одного - элемент b и не более одного - элемент с. Поэтому всего множеств не более $1 + 3 \cdot 1 = 4$, т. е. $k_{n} \leq 4$.
б) Существует элемент множества X, входящий в три трехэлементных множества, но никакой элемент множества X не входит более чем в три трехэлементных множества. Тогда, если $\{ a; b; c \}$ - одно из множеств, то любое из оставшихся множеств пересекается с ним, причем не более двух из этих оставшихся множеств содержит элемент а, не более двух - элемент b и не более двух - элемент с. Поэтому всего множеств не более $1 + 3 \cdot 2 = 7$, т. е. $k_{n} \leq 7$.
в) Существует элемент а множества X, принадлежащий по крайней мере четырем трехэлементным множествам. Тогда все остальные элементы этих четырех множеств различны, а любое из оставшихся множеств также должно содержать элемент а (иначе такое множество имело бы по одному различному общему элементу с каждым из четырех множеств, т. е. содержало бы по меньшей мере 4 элемента). Таким образом, в этом случае имеем $1 + 2 \cdot k_{n} \leq n$, т.е. $k_{n} \leq [(n - 1)/2]$.
Для $n = l, 2, 3, 4, 5$ имеем $k_{1} = k_{2} = 0, k_{3} = k_{4} = 1, k_{5} = 2$. Пусть $n = 6$. Тогда ни один элемент не принадлежит сразу трем множествам, иначе их объединение состояло бы из 7 элементов. Поэтому имеет место случай а) и $k_{0} \leq 4$. С другой стороны, существует пример четырех множеств: если $X = \{ a; b; c;d; e; f \}$, то трехэлементными подмножествами могут быть $\{ a; b; c \}, \{c; d; e \}, \{ e; f; a \}, \{b; d; f \}$. Таким образом, $k_{6} = 4$. Пусть $n \in \{7; 8; \cdots; 16 \}$. Тогда, если имеет место случай в), то количество множеств не превосходит $[(16 - 1)/2] = 7$; если же имеет место случай а) или б), то это количество также не превосходит 7. С другой стороны, если множество X среди своих элементов содержит 7 элементов a, b, c, d, е, f, g, то существует пример семи трехэлементных подмножеств: $\{a; b; c\}, \{c; d; e \}, \{e; f; a \}, \{ b; d; f \}, \{ a; g; d \}, \{b; g; e\}, \{c; g; f \}$. Таким образом, $k_{n} = 7$ при $n = 7, 8, 16$. Наконец, если $n \geq 17$, то в любом из случаев а), б), в) справедлива оценка $k_{n} \leq [(n - 1)/2]$, причем эта оценка достигается при следующем выборе трехэлементных подмножеств: один из элементов является общим для всех множеств, а остальные элементы (кроме, быть может, одного в случае четного я) разбиваются на пары и образуют с общим элементом требуемые подмножества. Таким образом,
$k_{n} = [(n - 1)/2]$ при $n \geq 17$.