Difference between revisions of "1981 IMO Problems/Problem 2"
m (→Solution 4) |
m (→Solution 5) |
||
(3 intermediate revisions by 2 users not shown) | |||
Line 62: | Line 62: | ||
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> | 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}} | {{alternate solutions}} | ||
− | {{IMO box|num-b=1|num-a=3|year= | + | {{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 |