Difference between revisions of "1981 IMO Problems/Problem 2"

Revision as of 13:02, 11 May 2019

Problem

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}.$

Solutions

Solution 1

Clearly, the sum of the desired least elements is $\sum_{k=1}^{n} k {n-k \choose r-1} = \sum_{k=1}^{n} {k \choose 1}{n-k \choose r-1}$ , which we claim to be equal to ${n+1 \choose r+1}$ by virtue of the following argument.

Consider a binary string of length $n+1$ which contains $r+1$ 1s. For some value of $k$ between 1 and $n$ , inclusive, we say that the second 1 will occur in the $(k+1)$ th place. Clearly, there are ${k \choose 1}$ ways to arrange the bits coming before the second 1, and ${n-k \choose r-1}$ ways to arrange the bits after the second 1. Our identity follows.

Since the sum of the least elements of the sets is ${n+1 \choose r+1}$ , the mean of the least elements is $\frac{{n+1 \choose r+1}}{{n \choose r}} = \frac{n+1}{r+1}$ , Q.E.D.

Solution 2

We proceed as in the previous solution, but we prove our identity using the following manipulations:

$\begin{matrix}\sum_{k=1}^{n}k{n-k \choose r-1 } &=&\sum_{k=1}^{n-(r-1)}{k}{n-k \choose r-1}\\ &=& \sum_{i=1}^{n-(r-1)}\sum_{k=i}^{n-(r-1)}{n-k \choose r-1}\\ &=&\sum_{i=1}^{n-(r-1)}{n-i+1 \choose r}\\ &=&{n+1 \choose r+1} \end{matrix}$

Q.E.D.

Solution 3

We proceed by strong induction.

We define $F(k, k-1)$ to be zero (the empty sum).

We consider $r$ to be fixed. The assertion obviously holds for $r = n$ . We now assume the problem to hold for values of $n$ less than or equal to $k$ . By considering subsets containing $k+1$ and not containing $k+1$ , respectively, we conclude that

$F(k+1, r) = \frac{{k \choose r-1}F(k,r-1) + {k \choose r}F(k,r)}{{k+1 \choose r}} = 1 + \frac{k-r+1}{r+1} = \frac{k+2}{r+1}$ .

This completes our induction, Q.E.D.

Solution 4

Consider a bipartite graph $G$ with bipartition $\{A,B\}$ . The vertices in $A$ are the $(r+1)$ -element subsets of $\{0, \dots , n\}$ , and the vertices in $B$ are the $r$ -element subsets of $\{1, \dots , n\}$ , and we draw an edge $\overline{ab}$ iff the subset $b \in B$ may be obtained from $a \in A$ by deleting the smallest element in $a$ .

Note that

$|A|=\binom{n+1}{r+1}, |B|=\binom{n}{r}, |E(G)|=\binom{n+1}{r+1}=\frac{n+1}{r+1} \binom{n}{r}.$

The degree of a vertex in $B$ is the value of the least element of its corresponding subset. Hence $F(n,r)=\frac{1}{\binom{n}{r}} \sum_{v \in B} \deg (v)= \frac{n+1}{r+1}.$ Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

1988 IMO (Problems) • Resources
Preceded by Problem 1	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 3
All IMO Problems and Solutions

@@ Line 64: / Line 64: @@
 {{alternate solutions}}
-{{IMO box|num-b=1|num-a=3|year=1981}}
+{{IMO box|num-b=1|num-a=3|year=1988}}
 [[Category:Olympiad Combinatorics Problems]]

Page

Toolbox

Search