Difference between revisions of "1981 IMO Problems/Problem 2"
m (→Solution 4) |
m (→Solution 5) |
||
(One intermediate revision by one other user not shown) | |||
Line 69: | Line 69: | ||
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. | 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 | + | 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> | + | 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 | Solution by Ilikeapos | ||
+ | |||
{{alternate solutions}} | {{alternate solutions}} | ||
Latest revision as of 11: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 |