Двойной подсчёт

Для трёх бюрократов из разных комиссий будем говорить, что и похожи для если либо знаком с обоими бюрократами и либо незнаком с обоими. Для каждой пары бюрократов из разных комиссий найдём количество бюрократов в третьей комиссии, для которых они похожи. Оценим сумму всех этих чисел. В каждой тройке бюрократов из разных комиссий есть либо две пары знакомых, либо две пары незнакомых между собой. Значит, два из них являются похожими для третьего, и вклад каждой тройки в сумму не менее Следовательно, сумма не меньше, чем число троек бюрократов, то есть:

Поэтому одно из слагаемых не меньше то есть не меньше Таким образом, какая-то пара бюрократов из разных комиссий является похожей не менее чем для бюрократов из третьей. Значит, эти два бюрократа либо знакомы хотя бы с бюрократами из оставшейся комиссии, либо незнакомы хотя бы с бюрократами из оставшейся комиссии.