IMO 1981 · Problem 2

Let \(1 \le r \le n\) and consider all subsets of \(r\) elements of the set \(\{1,2,\ldots,n\}\). Each of these subsets has a smallest member. Let \(F(n,r)\) denote the arithmetic mean of these smallest numbers; prove that \[ F(n,r)=\frac{n+1}{r+1}. \]

Official text of the problem. Official problem paper (PDF)

Solution

Let \(\mathcal S\) be the collection of all \(r\)-element subsets of \(\{1,\ldots,n\}\), and write \(m(S)=\min S\). We count the pairs \[ (S,t),\qquad S\in\mathcal S,\quad t\text{ an integer with }0\le t<m(S). \]

For each fixed \(S\), there are exactly \(m(S)\) choices of \(t\). Hence the number of pairs is \[ \sum_{S\in\mathcal S}m(S). \]

On the other hand, the map \[ (S,t)\longmapsto S\cup\{t\} \] is a bijection onto the collection of all \((r+1)\)-element subsets of \(\{0,1,\ldots,n\}\). Indeed, \(t\) is the smallest element of the resulting subset. Conversely, from any such subset \(T\), take \(t=\min T\) and \(S=T\setminus\{t\}\). Every element of \(S\) is positive and greater than \(t\), so this gives a valid pair and is the inverse map.

Therefore \[ \sum_{S\in\mathcal S}m(S)=\binom{n+1}{r+1}. \] There are \(\binom nr\) subsets in \(\mathcal S\), so their smallest members have arithmetic mean \[ F(n,r) =\frac{\displaystyle\binom{n+1}{r+1}} {\displaystyle\binom nr} =\frac{n+1}{r+1}. \] The argument holds for every \(1\le r\le n\), including both endpoints.

The solution was checked against John Scholes' IMO solution archive (Kalva).