Помогите разобраться (найти максимум подмножеств)

[Gaary_P]

Задача.
Пусть $M= {M_1, . . . ,M_s}$ — произвольная совокупность, состоящая из трехэлементных подмножеств $n$-элементного множества, причём $|M_i \bigcap M_j | \ne 1$ для любых i, j. Найдите максимум $s$, при котором это возможно.

Решение.
Всего трехэлементных подмножеств $n$-элементного множества равно $C_n^3$. Насколько я понимаю, теперь необходимо вычеркнуть минимальное количество подмножеств, так, чтобы из оставшихся подмножеств каждые два либо не пересекались, либо имели 2 общих элемента.

Не совсем понятно, как вычеркнуть эти подмножества. Может подскажете, что почитать можно?

[Deggial]

Название исправил на более содержательное.

Здесь можно решить руками: $|M_i \bigcap M_j | \ne 1$ и $|M_i|=3$ означает, что либо $M_i, M_j$ не пересекаются, либо $|M_i \bigcap M_j |=2$. Значит произвольная совокупность $M$ распадается на классы множеств, элементы которых не пересекаются, либо имеют общее для всех пересечение мощности 2. Получаем общее описание $M$, из него находим оптимальное.

[provincialka]

Не совсем так. Три множества могут пересекаться по-другому. Например, $\{1,2,3\},\{2,3,4\},\{1,2,4\}$

[Cash]

Есть еще вариант $\{123\}$; $\{234\}$; $\{124\}$; $\{134\}$

-- Ср окт 02, 2013 17:52:34 --

Сопоставляя всё вышесказанное, при $n=4m$ мы получим, что $s=n$, при других тоже сложностей не должно возникнуть.

[Gaary_P]

А откуда взялось, что при $n=4m$ $s=n$?

[provincialka]

Gaary_P в сообщении #770152 писал(а):

А откуда взялось, что при $n=4m$ $s=n$?

В этом случае множесто можно разбить на четверки элементов. А для каждой четверки прстроить 4 множества, как указал Cash. Значит, множеств будет столько же, сколько элементов. В остальных случаях множеств будет меньше, чем элементов.

[Gaary_P]

Так а как тогда доказать, что не может быть случая, когда множеств $M_i$ не может быть больше чем $n$?

[provincialka]

Рассмотрите другие классы множеств. Кроме "четверных" все остальные будут иметь тот вид, про который сказал Deggial, то есть все подмножества класса будут иметь 2оющих элемента. Сколько будет в таком классе элементов и подмножеств?