Продвинутый двойной подсчёт

Каждое ребро даёт вклад \(2\) в сумму степеней, значит сумма степеней равна \(2E\) и чётна. Сумма чётных степеней чётна, поэтому сумма нечётных степеней тоже чётна. Сумма нечётного количества нечётных чисел была бы нечётной, значит таких вершин чётное число.

Всего пар \((ученик, кружок)\), где ученик посещает кружок, равно \(120\cdot4=480\). Если бы каждый кружок имел не более \(31\) участника, пар было бы не более \(15\cdot31=465\), противоречие. Значит, некоторый кружок имеет хотя бы \(32\) участника.

Считаем пары \((клетка, линия)\), где линия — строка или столбец, содержащая отмеченную клетку. Каждая отмеченная клетка даёт \(2\) пары, всего \(140\). Линий \(24\). Среднее равно \(\frac{140}{24}>5\), значит некоторая линия содержит хотя бы \(6\) отмеченных клеток.

Правая часть \(2^n\) считает подмножества по независимому выбору: каждый элемент либо входит, либо не входит. Левая часть считает те же подмножества по размеру: сначала выбираем размер \(k\), затем само \(k\)-элементное подмножество. Это один и тот же набор объектов, значит тождество доказано.

Если сначала выбрать \(A\) размера \(k\), то отмеченный элемент \(x\in A\) выбирается \(k\) способами, получаем левую часть. Если сначала выбрать \(x\), есть \(n\) вариантов, а остальные элементы подмножества выбираются произвольно: \(2^{n-1}\) вариантов. Получаем \(n2^{n-1}\).

Число пар \((x,A)\), где \(x\in A\), не меньше \(18\cdot4=72\). Эти пары распределены между \(10\) элементами. Среднее число множеств на элемент не меньше \(7.2\), значит некоторый элемент входит хотя бы в \(8\) множеств.

Сумма степеней равна \(2E>(r-1)n\). Если бы все степени были не больше \(r-1\), сумма степеней была бы не больше \((r-1)n\), противоречие. Значит, есть вершина степени хотя бы \(r\).

Всего игр \(\binom n2\), и каждая игра даёт ровно одну победу. Среднее число побед на игрока равно \(\frac{\binom n2}{n}=\frac{n-1}{2}\). Поэтому кто-то имеет не меньше среднего, а кто-то не больше среднего.

Считаем пары \((A,\{x,y\})\), где \(A\subseteq[n]\) и \(x,y\in A\). Если сначала выбрать \(A\) размера \(k\), получаем \(\binom{k}{2}\binom nk\). Суммируем по \(k\). Если сначала выбрать \(\{x,y\}\), есть \(\binom n2\) способов, а остальные \(n-2\) элементов можно выбирать свободно: \(2^{n-2}\) способов.

Каждая строка с \(3\) отметками даёт \(\binom32=3\) пар столбцов. Всего таких появлений пар \(6\cdot3=18\). Всего пар столбцов \(\binom62=15\). Если бы каждая пара столбцов появлялась не более одного раза, появлений было бы не больше \(15\), противоречие. Значит, некоторая пара столбцов появляется хотя бы в двух строках.

Пусть \(d_i\) — число подмножеств, содержащих \(i\)-й элемент. Тогда \(\sum d_i=24\). Сумма размеров всех попарных пересечений равна \(\sum_{i=1}^5\binom{d_i}{2}\). При фиксированной сумме \(24\) эта величина минимальна при распределении \(5,5,5,5,4\), и равна \(46\). Если бы все попарные пересечения имели размер не больше \(1\), сумма была бы не больше \(\binom82=28\). Противоречие.

Всего решений не меньше \(30\cdot3=90\). Если каждую задачу решили не более \(14\) участников, всего решений было бы не больше \(6\cdot14=84\), противоречие. Значит, есть задача с хотя бы \(15\) решениями.

Каждое выбранное подмножество содержит \(\binom{k}{2}\) пар элементов, всего \(m\binom{k}{2}\) появлений пар. Но одна и та же пара элементов не может лежать в двух разных выбранных подмножествах, иначе эти два подмножества имели бы как минимум два общих элемента. Всего пар элементов в исходном множестве \(\binom n2\). Следовательно, \(m\binom{k}{2}\le\binom n2\).

Каждая строка даёт \(\binom r2\) пар отмеченных столбцов, всего \(n\binom r2\) появлений. По условию каждая пара столбцов появляется не более одного раза. Всего пар столбцов \(\binom n2\). Поэтому \(n\binom r2\le\binom n2\).

Зафиксируем среднюю вершину \(v_i\). Чтобы получить путь длины \(2\) с этой средней вершиной, надо выбрать две различные соседние вершины из \(d_i\) соседей: \(\binom{d_i}{2}\) способов. Каждый неупорядоченный путь длины \(2\) имеет ровно одну среднюю вершину, значит сумма по всем вершинам даёт точное число таких путей.

Пусть \(d_j\) — число учеников, решивших \(j\)-ю задачу. Тогда \(\sum d_j\ge21\cdot6=126\). Число троек \((\{u,v\}, задача)\), где оба ученика решили эту задачу, равно \(\sum_{j=1}^{10}\binom{d_j}{2}\). При сумме \(126\) по \(10\) задачам эта сумма минимальна при распределении \(13,13,13,13,13,13,12,12,12,12\), и равна \(6\binom{13}{2}+4\binom{12}{2}=732\). Пар учеников \(\binom{21}{2}=210\). Если бы каждая пара имела не более \(3\) общих задач, троек было бы не больше \(630\), противоречие. Значит, есть пара с не менее чем \(4\) общими задачами.

Если любые два выбранных подмножества пересекаются не более чем по одному элементу, то одна и та же пара элементов не может лежать в двух разных подмножествах. Тогда всего появлений пар не больше \(\binom{20}{2}=190\). Но каждое из \(30\) подмножеств размера \(6\) содержит \(\binom62=15\) пар, всего \(450\) появлений. Противоречие. Значит, два подмножества имеют хотя бы два общих элемента.

Каждое выбранное \(k\)-элементное множество содержит \(\binom{k}{t+1}\) подмножеств размера \(t+1\), всего \(m\binom{k}{t+1}\) появлений. Но одно и то же \((t+1)\)-элементное подмножество не может лежать в двух выбранных множествах: тогда эти два множества имели бы как минимум \(t+1\) общих элементов, что запрещено. Всего \((t+1)\)-подмножеств исходного множества \(\binom{n}{t+1}\). Получаем неравенство.

Число путей длины \(2\) равно \(\sum_i\binom{d_i}{2}\), где \(d_i\) — степени вершин. Функция \(\binom{x}{2}=\frac{x(x-1)}2\) выпукла, поэтому при фиксированной сумме \(\sum d_i=2m\) сумма \(\sum\binom{d_i}{2}\) не меньше \(n\binom{2m/n}{2}\). Если средняя степень \(\frac{2m}{n}>r\), то среднее значение \(\binom{d_i}{2}\) больше \(\binom r2\) в подходящем строгом смысле, значит некоторая вершина даёт больше \(\binom r2\) путей длины \(2\).

Сумма размеров всех попарных пересечений равна \(\sum_x\binom{d(x)}2\), потому что каждый элемент \(x\) вносит вклад в пары множеств, которые его содержат. При \(\sum d(x)\ge mr\) выпуклость даёт

\[\sum_x\binom{d(x)}2\ge n\binom{mr/n}{2}=\frac{mr(mr-n)}{2n}.\]

Пар множеств всего \(\binom m2\). Значит, средний размер попарного пересечения не меньше

\[\frac{\frac{mr(mr-n)}{2n}}{\binom m2}=\frac{r(mr-n)}{n(m-1)}.\]

Следовательно, одно из пересечений не меньше этого среднего.