#4 Counting in Two Ways

Each handshake corresponds to a pair of people. There are \(10\cdot9/2=45\) pairs.

There are \(20\cdot2=40\) pairs.

When summing by rows, each entry is counted once. When summing by columns, each entry is also counted once. Therefore the totals are equal.

Each of the \(12\) words gives \(5\) positions. Total: \(12\cdot5=60\) pairs.

Choose \(2\) vertices from \(6\): \(6\cdot5/2=15\).

The sum of degrees is \(2E\), hence even. The sum of degrees of even-degree vertices is even, so 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 average club size is \(60/8=7.5\). If every club had at most \(7\), the total would be at most \(56\), contradiction. Hence some club has at least \(8\).

Each of the \(5\) elements belongs to exactly half of all subsets, i.e. \(2^4=16\) subsets. The sum of subset sizes equals the number of pairs \((S,x)\), so it is \(5\cdot16=80\).

Choose \(x\) in \(6\) ways. For each \(x\), each of the other \(5\) elements either belongs to \(S\) or not: \(2^5\) ways. Total: \(6\cdot2^5=192\).

Choose the middle vertex \(B\) in \(6\) ways. Choose \(A\) in \(5\) ways and \(C\) in \(4\) ways. Total: \(6\cdot5\cdot4=120\).

From each of the \(n\) vertices, \(n-3\) diagonals are drawn, so there are \(n(n-3)\) diagonal endpoints. Each diagonal has two endpoints, so the number of diagonals is \(n(n-3)/2\).

If everyone solved at most \(3\) problems, the total would be at most \(25\cdot3=75\), less than \(100\). Therefore someone solved at least \(4\) problems.

By size \(S=k\): there are \(C(n,k)\) subsets and \(k\) choices of the marked element, giving the left side. By marked element: \(n\) choices for \(x\), and the other \(n-1\) elements are chosen freely for \(S\), \(2^{n-1}\) ways. This gives the right side.

Choose a three-element subset of \(\{1,\ldots,n+1\}\). If the largest element is \(t+1\), the other two are chosen from \(1,\ldots,t\), in \(C(t,2)\) ways. Summing over \(t=2,\ldots,n\) gives the left side, while the total number is \(C(n+1,3)\).

Total memberships: \(40\cdot2=80\). If every club had at most \(15\) students, the total would be at most \(5\cdot15=75\), contradiction. Hence some club has at least \(16\) students.

Each element is either outside \(B\), in \(B\) but not in \(A\), or in both sets. Three independent states for each of \(n\) elements give \(3^n\) pairs.

Choose \(2\) points out of \(12\). This gives \(12\cdot11/2=66\) segments.

There are \(n(n-1)/2\) games, each giving exactly one win. The average number of wins per player is \((n(n-1)/2)/n=(n-1)/2\). Hence some player has at least the average.

A \(5\) by \(6\) grid has \(6\) horizontal and \(7\) vertical lines. A rectangle is determined by choosing two vertical and two horizontal lines. Answer: \(C(7,2)C(6,2)=21\cdot15=315\).

Total memberships: \(12\cdot5=60\). The average number of committees per person is \(60/20=3\). Hence some person belongs to at least \(3\) committees.

Build the acquaintance graph. The sum of degrees is at least \(15\cdot7=105\). Each acquainted pair contributes twice to the degree sum, so the number of edges is at least \(105/2=52.5\). Since it is an integer, it is at least \(53\).

By size \(S=k\), there are \(k^2\) ways to choose the ordered pair \((x,y)\), giving the left side. Count by \((x,y)\). If \(x=y\), choose this element in \(n\) ways and choose the rest of \(S\) freely: \(2^{n-1}\). If \(x e y\), choose the ordered pair in \(n(n-1)\) ways and the remaining \(n-2\) elements freely: \(2^{n-2}\). Total: \(n2^{n-1}+n(n-1)2^{n-2}=n(n+1)2^{n-2}\).

By lines, there are \(9\cdot5=45\) incidences. If there are \(N\) points, counting by points gives \(3N\). Thus \(3N=45\), so \(N=15\).

Assume any two chosen triples share at most one element. Then no pair of elements can occur in two different triples; otherwise those two triples would share that pair, i.e. two common elements. Each triple contains \(3\) pairs, so \(17\) triples would contain \(51\) distinct element-pairs. But a \(10\)-element set has only \(10\cdot9/2=45\) pairs. Contradiction. Hence two triples share at least two elements.