Difference between revisions of "1981 IMO Problems/Problem 2"
(Added another solution) |
m (→Solution 5) |
||
(6 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | Let <math> | + | 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> | + | 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. | ||
Line 25: | Line 25: | ||
<center> | <center> | ||
<math> | <math> | ||
− | \begin{matrix} | + | \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} | \end{matrix} | ||
</math> | </math> | ||
Line 39: | Line 39: | ||
We proceed by strong induction. | We proceed by strong induction. | ||
− | We define <math> | + | We define <math>F(k, k-1)</math> to be zero (the empty sum). |
− | We consider <math> | + | 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 51: | Line 51: | ||
This completes our induction, Q.E.D. | This completes our induction, Q.E.D. | ||
− | {{ | + | ===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. | ||
− | + | Solution by Ilikeapos | |
− | + | {{alternate solutions}} | |
− | |||
+ | {{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
Contents
Problem
Let and consider all subsets of elements of the set . Each of these subsets has a smallest member. Let denote the arithmetic mean of these smallest numbers; prove that
Solutions
Solution 1
Clearly, the sum of the desired least elements is , which we claim to be equal to by virtue of the following argument.
Consider a binary string of length which contains 1s. For some value of between 1 and , inclusive, we say that the second 1 will occur in the th place. Clearly, there are ways to arrange the bits coming before the second 1, and ways to arrange the bits after the second 1. Our identity follows.
Since the sum of the least elements of the sets is , the mean of the least elements is , Q.E.D.
Solution 2
We proceed as in the previous solution, but we prove our identity using the following manipulations:
Q.E.D.
Solution 3
We proceed by strong induction.
We define to be zero (the empty sum).
We consider to be fixed. The assertion obviously holds for . We now assume the problem to hold for values of less than or equal to . By considering subsets containing and not containing , respectively, we conclude that
.
This completes our induction, Q.E.D.
Solution 4
Consider a bipartite graph with bipartition . The vertices in are the -element subsets of , and the vertices in are the -element subsets of , and we draw an edge iff the subset may be obtained from by deleting the smallest element in .
Note that
The degree of a vertex in is the value of the least element of its corresponding subset. Hence
Solution 5
We will count how many times each element of the set appear as the smallest element in a set, which will lead us to the result.
To count how many times appears as the smallest element of a subset, we need to choose an element subset from the remaining numbers, as all of them are greater than There are simply ways to do this.
Similarly, to count how many times appears as the smallest element, we need to choose an element subset from the remaining numbers greater than There are ways to do this.
As there are subsets, and thus smallest elements, in total, it now becomes clear that we need to evaluate the sum We can rearrange this sum as Using the Hockey Stick Identity on each of the smaller sums on the numerator gives us Using Hockey stick again gives us which simplifies to 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 |