Олимпиадная задача по классической комбинаторике для 8–11 классов: бюрократы и комиссии

  Рассмотрим граф, вершинами которого являются бюрократы, причём два бюрократа из разных комиссий соединены красным ребром, если они знакомы, и синим – в противном случае. Пусть в трёх комиссиях a, b и c бюрократов. Рассмотрим произвольных бюрократов A, B из первых двух комиссий. Пусть они знакомы. Тогда существует ровно 10 треугольников ABC, в которых все ребра красные. Аналогично для незнакомых A и B найдутся ровно 10 треугольников ABC, в которых все рёбра синие. Значит, общее число одноцветных треугольников равно 10ab. Аналогично оно же равно 10ac и 10bc, поэтому  a = b = c.

  Для трёх бюрократов A, B, C из разных комиссий, будем говорить, что B и C похожи для A, если A соединен с B и C ребрами одного цвета. Для каждого бюрократа найдём количество пар, похожих для него, и подсчитаем сумму s всех этих чисел двумя способами.

  С одной стороны, каждая пара бюрократов B, C из разных комиссий является похожей ровно для 20 бюрократов; всего таких пар 3a², следовательно,

s = 60a².  С другой стороны, в любом одноцветном треугольнике ABC каждые два бюрократа похожи для третьего; если же треугольник ABC разноцветный (скажем, ребро AB отличается по цвету от других), то в нём ровно одна пара  (A, B)  похожа для третьего. Так как количество одноцветных треугольников равно 10a², а разноцветных –  a³ – 10a²,  то  s = 30a² + (a³ – 10a²).  Значит,  60a² = a³ + 20a²,  откуда  a = 40.