IMO 1981 Problem 2
Fix integers $1 \le r \le n$.
Proposed by: -
Verified: no
Verdicts: UNKNOWN + PASS
Solve time: 11m36s
Problem
Let $\displaystyle 1 \le r \le n$ and consider all subsets of $\displaystyle r$ elements of the set ${ 1, 2, \ldots , n }$. Each of these subsets has a smallest member. Let $\displaystyle F(n,r)$ denote the arithmetic mean of these smallest numbers; prove that
$F(n,r) = \frac{n+1}{r+1}.$
Exploration
Fix integers $1 \le r \le n$. Each $r$-element subset of ${1,2,\dots,n}$ contributes a single distinguished value, its minimum. The quantity $F(n,r)$ is the average of these minima over all such subsets.
The smallest element of a subset is determined by a cutoff position: if the minimum equals $k$, then $k$ must belong to the subset and all remaining $r-1$ elements must lie in ${k+1,\dots,n}$. This yields a direct enumeration of subsets with fixed minimum.
The main difficulty is evaluating the weighted sum of minima across all subsets without double counting or losing track of dependence between $k$ and the remaining choices. A direct summation leads to expressions of the form $\sum k \binom{n-k}{r-1}$, which require a nontrivial combinatorial identity or a telescoping transformation.
A more stable approach replaces the distribution of minima by a decomposition of binomial sums, reducing everything to standard identities for sums of binomial coefficients and their first moments.
For small cases, when $n=3$ and $r=2$, the subsets are ${1,2}, {1,3}, {2,3}$ with minima $1,1,2$, giving average $4/3$. The formula predicts $(3+1)/(2+1)=4/3$. For $n=4$, $r=2$, the subsets yield minima $1,1,1,2,2,3$, averaging $10/6=5/3$, matching $(4+1)/3$. These computations support the claimed expression.
The central structure is therefore a weighted binomial sum whose simplification must produce a rational function depending only on $n$ and $r$.
Problem Understanding
The task is to compute the average value of the smallest element taken over all $r$-element subsets of ${1,2,\dots,n}$. Each subset contributes exactly one integer between $1$ and $n-r+1$, and the distribution of these minima is highly nonuniform.
This is a Type C problem since a specific closed-form value must be determined:
$$F(n,r)=\frac{n+1}{r+1}.$$
The core difficulty lies in converting a combinatorial distribution into an algebraic identity without introducing errors in the dependence between the minimum and the remaining elements of the subset.
Proof Architecture
First, a lemma determines the number of subsets whose minimum equals a fixed integer $k$, expressed as $\binom{n-k}{r-1}$.
Second, a lemma rewrites the total sum of minima as $\sum_{k=1}^{n-r+1} k \binom{n-k}{r-1}$ divided by $\binom{n}{r}$.
Third, a lemma evaluates the binomial sum $\sum_{k=1}^{n-r+1} k \binom{n-k}{r-1}$ by the substitution $j=n-k$, reducing it to sums of the forms $\sum \binom{j}{r-1}$ and $\sum j\binom{j}{r-1}$.
Fourth, an identity transforms $j\binom{j}{r-1}$ into a linear combination involving $\binom{j+1}{r}$ and $\binom{j}{r-1}$, enabling telescoping.
Fifth, standard binomial summation identities yield closed forms for these sums.
The hardest step is the evaluation of $\sum j\binom{j}{r-1}$, where a direct approach fails without a structural transformation.
Solution
Let $\mathcal{S}_{n,r}$ denote the set of all $r$-element subsets of ${1,2,\dots,n}$. The cardinality of this set equals $\binom{n}{r}$.
For each $k$ with $1 \le k \le n-r+1$, let $A_k$ denote the family of subsets in $\mathcal{S}_{n,r}$ whose minimum equals $k$. Any set in $A_k$ must contain $k$, and the remaining $r-1$ elements must be chosen from ${k+1,\dots,n}$, which contains $n-k$ elements. Hence the number of such subsets equals $\binom{n-k}{r-1}$.
The total sum of minima over all subsets equals
$$\sum_{k=1}^{n-r+1} k \binom{n-k}{r-1}.$$
Therefore,
$$F(n,r)=\frac{1}{\binom{n}{r}} \sum_{k=1}^{n-r+1} k \binom{n-k}{r-1}.$$
Introduce the substitution $j=n-k$. Then $k=n-j$, and as $k$ runs from $1$ to $n-r+1$, the index $j$ runs from $n-1$ down to $r-1$. Rewriting the sum gives
$$\sum_{k=1}^{n-r+1} k \binom{n-k}{r-1} = \sum_{j=r-1}^{n-1} (n-j)\binom{j}{r-1}.$$
Expanding,
$$\sum_{j=r-1}^{n-1} (n-j)\binom{j}{r-1} = n\sum_{j=r-1}^{n-1}\binom{j}{r-1} - \sum_{j=r-1}^{n-1} j\binom{j}{r-1}.$$
The first sum satisfies
$$\sum_{j=r-1}^{n-1}\binom{j}{r-1}=\binom{n}{r},$$
since it counts all $r$-element subsets of ${1,\dots,n}$ by their minimum.
For the second sum, the identity
$$j\binom{j}{r-1} = r\binom{j+1}{r} - \binom{j}{r-1}$$
holds, since
$$\binom{j+1}{r}=\frac{j+1}{r}\binom{j}{r-1}$$
implies
$$r\binom{j+1}{r}=(j+1)\binom{j}{r-1}.$$
Subtracting $\binom{j}{r-1}$ from both sides yields the stated relation.
Summing over $j$ from $r-1$ to $n-1$ gives
$$\sum_{j=r-1}^{n-1} j\binom{j}{r-1} = r\sum_{j=r-1}^{n-1}\binom{j+1}{r} - \sum_{j=r-1}^{n-1}\binom{j}{r-1}.$$
The second term equals $\binom{n}{r}$. For the first term, the index shift $t=j+1$ transforms it into
$$\sum_{t=r}^{n}\binom{t}{r}=\binom{n+1}{r+1}.$$
Hence
$$\sum_{j=r-1}^{n-1} j\binom{j}{r-1} = r\binom{n+1}{r+1}-\binom{n}{r}.$$
Substituting both evaluations yields
$$\sum_{j=r-1}^{n-1} (n-j)\binom{j}{r-1} = n\binom{n}{r} - \left(r\binom{n+1}{r+1}-\binom{n}{r}\right).$$
This simplifies to
$$(n+1)\binom{n}{r}-r\binom{n+1}{r+1}.$$
Using
$$\binom{n+1}{r+1}=\frac{n+1}{r+1}\binom{n}{r},$$
we obtain
$$(n+1)\binom{n}{r}-r\cdot \frac{n+1}{r+1}\binom{n}{r} = \frac{n+1}{r+1}\binom{n}{r}.$$
Therefore,
$$F(n,r)=\frac{1}{\binom{n}{r}} \cdot \frac{n+1}{r+1}\binom{n}{r} = \frac{n+1}{r+1}.$$
This completes the computation.
Verification of Key Steps
The identity $\sum_{j=r-1}^{n-1}\binom{j}{r-1}=\binom{n}{r}$ can be reconstructed by classifying each $r$-subset of ${1,\dots,n}$ according to its minimum $k$, since each such subset corresponds uniquely to a choice of $r-1$ elements from ${k+1,\dots,n}$.
The transformation $j\binom{j}{r-1}=r\binom{j+1}{r}-\binom{j}{r-1}$ follows from rewriting $\binom{j+1}{r}$ as $\frac{j+1}{r}\binom{j}{r-1}$ and rearranging algebraically, which preserves equality for all integers $j \ge r-1$.
The substitution step from $k$-summation to $j$-summation preserves all indices because the mapping $j=n-k$ is bijective between ${1,\dots,n-r+1}$ and ${r-1,\dots,n-1}$.
Alternative Approaches
A different method assigns to each element $x \in {1,\dots,n}$ the probability that it is the minimum of a random $r$-subset, leading to a direct computation of $F(n,r)$ via symmetry of orderings in $(r+1)$-element subsets. This approach avoids weighted binomial sums and instead reduces the problem to uniform counting of relative orderings, yielding the same value $\frac{n+1}{r+1}$ with less algebraic manipulation.