1981 IMO Problems/Problem 2
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.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.