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"

 
m (→‎Solution 5)
 
(7 intermediate revisions by 5 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
  
−
Let <math> \displaystyle 1 \le r \le n </math> and consider all subsets of <math> \displaystyle r </math> elements of the set <math> \{ 1, 2, \ldots , n \} </math>.  Each of these subsets has a smallest member.  Let <math> \displaystyle F(n,r) </math> denote the arithmetic mean of these smallest numbers; prove that
+
Let <math>1 \le r \le n </math> and consider all subsets of <math>r </math> elements of the set <math> \{ 1, 2, \ldots , n \} </math>.  Each of these subsets has a smallest member.  Let <math>F(n,r) </math> denote the arithmetic mean of these smallest numbers; prove that
  
 
<center>
 
<center>
Line 15: Line 15:
 
Clearly, the sum of the desired least elements is <math> \sum_{k=1}^{n} k {n-k \choose r-1} = \sum_{k=1}^{n} {k \choose 1}{n-k \choose r-1} </math>, which we claim to be equal to <math>{n+1 \choose r+1} </math> by virtue of the following argument.
 
Clearly, the sum of the desired least elements is <math> \sum_{k=1}^{n} k {n-k \choose r-1} = \sum_{k=1}^{n} {k \choose 1}{n-k \choose r-1} </math>, which we claim to be equal to <math>{n+1 \choose r+1} </math> by virtue of the following argument.
  
−
Consider a binary string of length <math> \displaystyle n+1 </math> which contains <math> \displaystyle r+1 </math> 1s.  For some value of <math>k</math> between 1 and <math>\displaystyle n</math>, inclusive, we say that the second 1 will occur in the <math> \displaystyle (k+1) </math>th place.  Clearly, there are <math> {k \choose 1} </math> ways to arrange the bits coming before the second 1, and <math>{n-k \choose r-1} </math> ways to arrange the bits after the second 1.  Our identity follows.
+
Consider a binary string of length <math>n+1 </math> which contains <math>r+1 </math> 1s.  For some value of <math>k</math> between 1 and <math>n</math>, inclusive, we say that the second 1 will occur in the <math>(k+1) </math>th place.  Clearly, there are <math> {k \choose 1} </math> ways to arrange the bits coming before the second 1, and <math>{n-k \choose r-1} </math> ways to arrange the bits after the second 1.  Our identity follows.
  
 
Since the sum of the least elements of the sets is <math>{n+1 \choose r+1}</math>, the mean of the least elements is <math>\frac{{n+1 \choose r+1}}{{n \choose r}} = \frac{n+1}{r+1}</math>, Q.E.D.
 
Since the sum of the least elements of the sets is <math>{n+1 \choose r+1}</math>, the mean of the least elements is <math>\frac{{n+1 \choose r+1}}{{n \choose r}} = \frac{n+1}{r+1}</math>, Q.E.D.
  
 
=== Solution 2 ===
 
=== Solution 2 ===
 +
 +
We proceed as in the previous solution, but we prove our identity using the following manipulations:
 +
 +
<center>
 +
<math>
 +
\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}
 +
</math>
 +
</center>
 +
 +
Q.E.D.
 +
 +
=== Solution 3 ===
  
 
We proceed by strong induction.
 
We proceed by strong induction.
  
−
We define <math>\displaystyle F(k, k-1)</math> to be zero (the empty sum).
+
We define <math>F(k, k-1)</math> to be zero (the empty sum).
  
−
We consider <math> \displaystyle r</math> to be fixed.  The assertion obviously holds for <math>\displaystyle r = n</math>.  We now assume the problem to hold for values of <math>\displaystyle n</math> less than or equal to <math> \displaystyle k</math>.  By considering subsets containing <math>\displaystyle k+1</math> and not containing <math>\displaystyle k+1</math>, respectively, we conclude that
+
We consider <math>r</math> to be fixed.  The assertion obviously holds for <math>r = n</math>.  We now assume the problem to hold for values of <math>n</math> less than or equal to <math>k</math>.  By considering subsets containing <math>k+1</math> and not containing <math>k+1</math>, respectively, we conclude that
  
 
<center>
 
<center>
Line 35: Line 51:
 
This completes our induction, Q.E.D.
 
This completes our induction, Q.E.D.
  
−
{{alternate solutions}}
+
===Solution 4===
 +
 
 +
Consider a bipartite graph <math>G</math> with bipartition <math>\{A,B\}</math>. The vertices in <math>A</math> are the <math>(r+1)</math>-element subsets of <math>\{0, \dots , n\}</math>, and the vertices in <math>B</math> are the <math>r</math>-element subsets of <math>\{1, \dots , n\}</math>, and we draw an edge <math>\overline{ab}</math> iff the subset <math>b \in B</math> may be obtained from <math>a \in A</math> by deleting the smallest element in <math>a</math>.
 +
 
 +
Note that
 +
 
 +
<center>
 +
<math>|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}.</math>
 +
</center>
 +
 
 +
The degree of a vertex in <math>B</math> is the value of the least element of its corresponding subset. Hence <cmath>F(n,r)=\frac{1}{\binom{n}{r}} \sum_{v \in B} \deg (v)= \frac{n+1}{r+1}.</cmath>
 +
 
 +
===Solution 5===
 +
 
 +
We will count how many times each element of the set <math>\{1, 2, \ldots, n\}</math> appear as the smallest element in a set, which will lead us to the result.
 +
 
 +
To count how many times <math>1</math> appears as the smallest element of a subset, we need to choose an <math>r-1</math> element subset from the remaining <math>n - 1</math> numbers, as all of them are greater than <math>1.</math> There are simply <math>\dbinom{n - 1}{r - 1}</math> ways to do this.
 +
 
 +
Similarly, to count how many times <math>2</math> appears as the smallest element, we need to choose an <math>r - 1</math> element subset from the remaining <math>n - 2</math> numbers greater than <math>2.</math> There are <math>\dbinom{n - 2}{r - 1}</math> ways to do this.
 +
 
 +
As there are <math>\dbinom{n}{r}</math> subsets, and thus smallest elements, in total, it now becomes clear that we need to evaluate the sum <cmath>\frac{\binom{n - 1}{r - 1} + 2\binom{n - 2}{r - 1} + \cdots + (n - r + 1)\binom{r - 1}{r - 1}}{\binom{n}{r}}.</cmath> We can rearrange this sum as <cmath>\frac{\left(\binom{n - 1}{r - 1} + \binom{n - 2}{r - 1} + \cdots + \binom{r - 1}{r - 1}\right)+\left(\binom{n - 2}{r - 1} + \binom{n - 3}{r - 1} + \cdots + \binom{r - 1}{r - 1}\right)+\cdots+ \binom{r-1}{r-1}}{\binom{n}{r}}.</cmath> Using the Hockey Stick Identity on each of the smaller sums on the numerator gives us <cmath>\frac{\binom{n}{r} + \binom{n - 1}{r} + \binom{n-2}{r} + \cdots + \binom{r}{r}}{\binom{n}{r}}.</cmath> Using Hockey stick again gives us <cmath>\frac{\binom{n + 1}{r + 1}}{\binom{n}{r}},</cmath> which simplifies to <cmath>\frac{\frac{(n + 1)!}{(r + 1)!(n-r)!}}{\frac{n!}{r!(n-r)!}} = \left(\frac{(n + 1)!}{(r + 1)!(n - r)!}\right) \left(\frac{r!(n-r)!}{n!}\right) = \frac{n + 1}{r + 1},</cmath> as desired.
  
−
== Resources ==
+
Solution by Ilikeapos
  
−
* [[1981 IMO Problems]]
+
{{alternate solutions}}
−
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=366639#p366639 Discussion on AoPS/Mathlinks]
 
  
 +
{{IMO box|num-b=1|num-a=3|year=1981}}
  
 
[[Category:Olympiad Combinatorics Problems]]
 
[[Category:Olympiad Combinatorics Problems]]

Latest revision as of 10:18, 27 June 2020

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}.\]

Solution 5

We will count how many times each element of the set $\{1, 2, \ldots, n\}$ appear as the smallest element in a set, which will lead us to the result.

To count how many times $1$ appears as the smallest element of a subset, we need to choose an $r-1$ element subset from the remaining $n - 1$ numbers, as all of them are greater than $1.$ There are simply $\dbinom{n - 1}{r - 1}$ ways to do this.

Similarly, to count how many times $2$ appears as the smallest element, we need to choose an $r - 1$ element subset from the remaining $n - 2$ numbers greater than $2.$ There are $\dbinom{n - 2}{r - 1}$ ways to do this.

As there are $\dbinom{n}{r}$ subsets, and thus smallest elements, in total, it now becomes clear that we need to evaluate the sum \[\frac{\binom{n - 1}{r - 1} + 2\binom{n - 2}{r - 1} + \cdots + (n - r + 1)\binom{r - 1}{r - 1}}{\binom{n}{r}}.\] We can rearrange this sum as \[\frac{\left(\binom{n - 1}{r - 1} + \binom{n - 2}{r - 1} + \cdots + \binom{r - 1}{r - 1}\right)+\left(\binom{n - 2}{r - 1} + \binom{n - 3}{r - 1} + \cdots + \binom{r - 1}{r - 1}\right)+\cdots+ \binom{r-1}{r-1}}{\binom{n}{r}}.\] Using the Hockey Stick Identity on each of the smaller sums on the numerator gives us \[\frac{\binom{n}{r} + \binom{n - 1}{r} + \binom{n-2}{r} + \cdots + \binom{r}{r}}{\binom{n}{r}}.\] Using Hockey stick again gives us \[\frac{\binom{n + 1}{r + 1}}{\binom{n}{r}},\] which simplifies to \[\frac{\frac{(n + 1)!}{(r + 1)!(n-r)!}}{\frac{n!}{r!(n-r)!}} = \left(\frac{(n + 1)!}{(r + 1)!(n - r)!}\right) \left(\frac{r!(n-r)!}{n!}\right) = \frac{n + 1}{r + 1},\] as desired.

Solution by Ilikeapos

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

1981 IMO (Problems) • Resources
Preceded by
Problem 1 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 3
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1981_IMO_Problems/Problem_2&oldid=126713"