Олимпиадная задача по теории графов: 300 бюрократов и комиссии, 8–10 класс

Для трёх бюрократов A, B, C из разных комиссий, будем говорить, что B и C похожи для A, если A либо знаком с обоими бюрократами B и C, либо незнаком с обоими. Для каждой пары бюрократов из разных комиссий найдём количество бюрократов в третьей комиссии, для которых они похожи. Оценим сумму s всех этих 3·100·100 чисел. В каждой тройке бюрократов A, B, C из разных комиссий есть либо две пары знакомых, либо две пары незнакомых между собой. Значит, два из них являются похожими для третьего, и вклад каждой тройки в сумму s не меньше 1. Следовательно, сумма s не меньше, чем число троек бюрократов, то есть  s ≥ 100·100·100 = 10⁶,  и поэтому одно из слагаемых не меньше  10⁶ : (3·10⁴) = 100 : 3,  то есть не меньше 34. Таким образом, какая-то пара бюрократов из разных комиссий является похожей не меньше чем для 34 бюрократов из третьей. Значит, эти два бюрократа либо знакомы хотя бы с 17 бюрократами из оставшейся комиссии, либо незнакомы хотя бы с 17 бюрократами из оставшейся комиссии.

Ответ задачи отсутствует