Difference between revisions of "1981 IMO Problems/Problem 2"
(template) |
(+Solution 4) |
||
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> | ||
{{alternate solutions}} | {{alternate solutions}} | ||
Revision as of 15:55, 7 August 2015
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 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 |