Задача 026 — Задачи на Графы

В городе 2015 жителей, которые организовали $n$ клубов. Оказалось, что для каждых двух клубов количество жителей, состоящих хотя бы в одном из них, не больше 2011. Однако для любых трёх клубов хотя бы в одном из них состоит каждый житель города. Найдите наибольшее возможное значение $n$ .

Подсказка

По первому условию для каждых двух клубов $A$ и $B$ найдутся 4 человека, которые в этих клубах не состоят. Но по второму условию эти 4 человека состоят во всех оставшихся клубах.

Решение

Ответ: 32.

Решение: Оценка. По первому условию для каждых двух клубов $A$ и $B$ найдутся 4 человека, которые в этих клубах не состоят. Но по второму условию эти 4 человека состоят во всех оставшихся клубах. Отсюда следует, что четверки, соответствующие разным парам клубов, не пересекаются. Отсюда $4 C_{n}^{2}<2015$ , то есть $n \leq 32$ . Пример. Выделим среди жителей города $C_{32}^{2}=496$ непересекающихся четверок. Каждой из них поставим в соответствие пару клубов, в которых жители, входящие в неё, они не состоят, так, чтобы каждой паре клубов соответствовала какая-то четверка. Остальные (не входящие в четверки) жители состоят во всех клубах.