Sunday, February 4, 2007

Mean. Topic: Algebra/Probability & Combinatorics/Calculus. Level: Olympiad.

Problem: (1983 Canada - #5) Show that the geometric mean of a set $ S $ of positive numbers equals the geometric mean of the geometric means of all non-empty subsets of $ S $. [Reworded]

Solution: Let $ S = \{a_1, a_2, \ldots, a_n\} $, so the geometric mean is $ (a_1a_2 \cdots a_n)^{\frac{1}{n}} $. We will show that the geometric mean of the geometric means of all non-empty subsets of $ S $ is equivalent to this. It suffices to show it is true for an arbitrary $ a_i $. Consider dividing the subsets of $ S $ that contain $ a_i $ into groups based on the number of elements it contains. We will count how many of them there are:

$ 1 $-element subsets containing $ a_i $ - clearly just the set $ \{a_i\} $. There is only $ 1 $;

$ 2 $-element subsets containing $ a_i $ - the set $ \{a_i, a_j\} $ for any $ j \neq i $. There are $ (n-1)C1 $ of these;

$ 3 $-element subsets containing $ a_i $ - there are $ (n-1)C2 $ of these.

It's pretty clear that if we want a $ k $-element subset containing $ a_i $ we are free to choose the other $ k-1 $ elements from the remaining $ n-1 $ elements of $ S $. If we take the geometric mean of these subsets, however, we find that

$ 1 $-element subsets give a full power of $ a_i $;

$ 2 $-element subsets give a $ \frac{1}{2} $ power of $ a_i $;

$ 3 $-element subsets give a $ \frac{1}{3} $ power of $ a_i $;

and so on. So when we multiply these all together, we get an exponent of

$ \displaystyle 1+(n-1)C1 \cdot \frac{1}{2}+(n-1)C2 \cdot \frac{1}{3}+ \cdots +(n-1)C(n-1) \cdot \frac{1}{n} = \sum_{k=1}^n \frac{1}{k} \cdot (n-1)C(k-1) $.

It remains to evaluate this sum, but we can do that through generating functions. Since $ \displaystyle (1+x)^{n-1} = \sum_{k=1}^n (n-1)C(k-1) \cdot x^{k-1} $, we integrate both sides to get

$ \displaystyle \frac{(1+x)^n}{n} = C+\sum_{k=1}^n \frac{1}{k}(n-1)C(k-1) \cdot x^k $.

Using $ x = 0 $, we obtain $ C = \frac{1}{n} $, so $ \displaystyle \frac{(1+x)^n-1}{n} = \sum_{k=1}^n \frac{1}{k}(n-1)C(k-1) \cdot x^k $.

Finally, by the substitution $ x = 1 $, we get the desired summation:

$ \displaystyle \sum_{k=1}^n \frac{1}{n} \cdot (n-1)C(k-1) = \frac{2^n-1}{n} $.

So prior to the last geometric mean, we have $ (a_i)^{\frac{2^n-1}{n}} $, but we know that there are $ 2^n-1 $ non-empty subsets of $ S $, which means the last geometric mean is a power of $ \frac{1}{2^n-1} $, and we have

$ \left(a_i^{\frac{2^n-1}{n}}\right)^{\frac{1}{2^n-1}} = (a_i)^{\frac{1}{n}} $,

the same power as the original geometric mean we computed. QED.

--------------------

Comment: A very nice problem because it branched together several aspects of mathematics all into a single problem, which is always cool. There is probably a non-calculus method of evaluating that sum, but basically any time you see a sum like that you can use generating functions and then apply derivatives/integrals to make it what you want. Apparantly a symmetry argument can also be made, but that's probably just the lazy way to do this problem...

--------------------

Practice Problem: (1983 Canada - #4) Given an arbitrary prime $ p $, show that we can find infinitely many positive integers $ n $ such that $ 2^n-n $ is a multiple of $ p $.

2 comments:

  1. Your solution seems a little complicated; why not simply multiply together the geometric means of all k-subsets at a time? Then it's clear that every element appears equally often, and it's also clear that the expression is of the right degree of homogeneity (by induction).

    ReplyDelete
  2. You are very tricksy... that's almost what I did anyway, though. I just did a lot of explaining to arrive at the solution. And as I said, I didn't make many symmetry arguments =).

    ReplyDelete