Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

 
(Added another solution)
Line 20: Line 20:
  
 
=== Solution 2 ===
 
=== Solution 2 ===
 +
 +
We proceed as in the previous solution, but we prove our identity using the following manipulations:
 +
 +
<center>
 +
<math>
 +
\begin{matrix} \displaystyle \sum_{k=1}^{n}k{n-k \choose r-1 } &=& \displaystyle \sum_{k=1}^{n-(r-1)}{k}{n-k \choose r-1}\\
 +
&=& \displaystyle  \sum_{i=1}^{n-(r-1)}\sum_{k=i}^{n-(r-1)}{n-k \choose r-1}\\
 +
&=& \displaystyle \sum_{i=1}^{n-(r-1)}{n-i+1 \choose r}\\
 +
&=& \displaystyle {n+1 \choose r+1}
 +
\end{matrix}
 +
</math>
 +
</center>
 +
 +
Q.E.D.
 +
 +
=== Solution 3 ===
  
 
We proceed by strong induction.
 
We proceed by strong induction.

Revision as of 15:56, 29 October 2006

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

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 $\displaystyle n+1$ which contains $\displaystyle r+1$ 1s. For some value of $k$ between 1 and $\displaystyle n$, inclusive, we say that the second 1 will occur in the $\displaystyle (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} \displaystyle \sum_{k=1}^{n}k{n-k \choose r-1 } &=& \displaystyle \sum_{k=1}^{n-(r-1)}{k}{n-k \choose r-1}\\ &=& \displaystyle \sum_{i=1}^{n-(r-1)}\sum_{k=i}^{n-(r-1)}{n-k \choose r-1}\\ &=& \displaystyle \sum_{i=1}^{n-(r-1)}{n-i+1 \choose r}\\ &=& \displaystyle {n+1 \choose r+1} \end{matrix}$

Q.E.D.

Solution 3

We proceed by strong induction.

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

We consider $\displaystyle r$ to be fixed. The assertion obviously holds for $\displaystyle r = n$. We now assume the problem to hold for values of $\displaystyle n$ less than or equal to $\displaystyle k$. By considering subsets containing $\displaystyle k+1$ and not containing $\displaystyle 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.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1981_IMO_Problems/Problem_2&oldid=10487"