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$.