Advanced Double Counting

Each edge contributes \(2\) to the degree sum, so the sum of degrees is \(2E\), even. The sum of even degrees is even, hence the sum of odd degrees is even. A sum of an odd number of odd integers would be odd, so the number of odd-degree vertices is even.

The number of pairs \((student, club)\) where the student attends the club is \(120\cdot4=480\). If every club had at most \(31\) members, there would be at most \(15\cdot31=465\) such pairs, a contradiction. Hence some club has at least \(32\) members.

Count pairs \((cell, line)\), where the line is a row or column containing the marked cell. Each marked cell gives \(2\) pairs, so there are \(140\). There are \(24\) lines. The average is \(\frac{140}{24}>5\), so some line contains at least \(6\) marked cells.

The right side \(2^n\) counts subsets by independent choices: each element is either included or not. The left side counts the same subsets by size: choose the size \(k\), then choose the \(k\)-element subset. These are the same objects, so the identity follows.

If we first choose \(A\) of size \(k\), then the marked element \(x\in A\) can be chosen in \(k\) ways, giving the left side. If we first choose \(x\), there are \(n\) choices, and the remaining elements of the subset are chosen freely: \(2^{n-1}\) choices. This gives \(n2^{n-1}\).

The number of pairs \((x,A)\), where \(x\in A\), is at least \(18\cdot4=72\). These pairs are distributed among \(10\) elements. The average number of sets containing an element is at least \(7.2\), so some element belongs to at least \(8\) sets.

The sum of degrees is \(2E>(r-1)n\). If all degrees were at most \(r-1\), the sum of degrees would be at most \((r-1)n\), a contradiction. Hence some vertex has degree at least \(r\).

There are \(\binom n2\) games, and each game gives exactly one win. The average number of wins per player is \(\frac{\binom n2}{n}=\frac{n-1}{2}\). Therefore someone has at least the average, and someone has at most the average.

Count pairs \((A,\{x,y\})\), where \(A\subseteq[n]\) and \(x,y\in A\). If we first choose \(A\) of size \(k\), we get \(\binom{k}{2}\binom nk\). Summing over \(k\) gives the left side. If we first choose \(\{x,y\}\), there are \(\binom n2\) choices, and the remaining \(n-2\) elements are free: \(2^{n-2}\) choices.

Each row with \(3\) marks gives \(\binom32=3\) pairs of columns. There are \(6\cdot3=18\) pair occurrences. There are only \(\binom62=15\) pairs of columns. If each pair appeared at most once, there would be at most \(15\) occurrences, a contradiction. Hence some pair of columns appears in at least two rows.

Let \(d_i\) be the number of subsets containing the \(i\)-th element. Then \(\sum d_i=24\). The sum of all pairwise intersection sizes is \(\sum_{i=1}^5\binom{d_i}{2}\). With fixed sum \(24\), this is minimised by the balanced distribution \(5,5,5,5,4\), giving \(46\). If every pairwise intersection had size at most \(1\), the sum would be at most \(\binom82=28\). Contradiction.

The total number of solved-problem incidences is at least \(30\cdot3=90\). If each problem were solved by at most \(14\) participants, the total would be at most \(6\cdot14=84\), a contradiction. Hence some problem was solved by at least \(15\) participants.

Each chosen subset contains \(\binom{k}{2}\) pairs of elements, giving \(m\binom{k}{2}\) pair occurrences. But the same pair of elements cannot lie in two different chosen subsets; otherwise those two subsets would share at least two elements. The whole ground set has only \(\binom n2\) pairs. Therefore \(m\binom{k}{2}\le\binom n2\).

Each row gives \(\binom r2\) pairs of marked columns, for a total of \(n\binom r2\) occurrences. By the condition, each pair of columns appears at most once. There are \(\binom n2\) column pairs in total. Hence \(n\binom r2\le\binom n2\).

Fix the middle vertex \(v_i\). To form a length-\(2\) path with this middle vertex, choose two distinct neighbours among its \(d_i\) neighbours: \(\binom{d_i}{2}\) ways. Each unordered length-\(2\) path has exactly one middle vertex, so summing over all vertices gives the exact number.

Let \(d_j\) be the number of students who solved problem \(j\). Then \(\sum d_j\ge21\cdot6=126\). The number of triples \((\{u,v\}, problem)\), where both students solved the problem, is \(\sum_{j=1}^{10}\binom{d_j}{2}\). With total \(126\) over \(10\) problems, this sum is minimised by the balanced distribution \(13,13,13,13,13,13,12,12,12,12\), giving \(6\binom{13}{2}+4\binom{12}{2}=732\). There are \(\binom{21}{2}=210\) pairs of students. If every pair had at most \(3\) common solved problems, there would be at most \(630\) triples, a contradiction. Hence some pair has at least \(4\) common solved problems.

If any two chosen subsets intersect in at most one element, then the same pair of elements cannot lie in two different subsets. Thus the total number of pair occurrences is at most \(\binom{20}{2}=190\). But each of the \(30\) subsets of size \(6\) contains \(\binom62=15\) pairs, for \(450\) occurrences. Contradiction. Hence two subsets have at least two common elements.

Each chosen \(k\)-element set contains \(\binom{k}{t+1}\) subsets of size \(t+1\), giving \(m\binom{k}{t+1}\) occurrences. But the same \((t+1)\)-element subset cannot lie in two chosen sets; otherwise those two sets would have at least \(t+1\) common elements, which is forbidden. The ground set has \(\binom{n}{t+1}\) such subsets in total. The inequality follows.

The number of length-\(2\) paths is \(\sum_i\binom{d_i}{2}\), where \(d_i\) are vertex degrees. The function \(\binom{x}{2}=\frac{x(x-1)}2\) is convex, so for fixed sum \(\sum d_i=2m\), the sum \(\sum\binom{d_i}{2}\) is at least \(n\binom{2m/n}{2}\). If the average degree \(\frac{2m}{n}>r\), then the average value of \(\binom{d_i}{2}\) is greater than \(\binom r2\) in the needed strict sense, so some vertex contributes more than \(\binom r2\) length-\(2\) paths.

The sum of all pairwise intersection sizes is \(\sum_x\binom{d(x)}2\), because each element \(x\) contributes to pairs of sets containing it. Since \(\sum d(x)\ge mr\), convexity gives

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

There are \(\binom m2\) pairs of sets. Hence the average pairwise intersection size is at least

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

Therefore one intersection is at least this average.