Canadian MO, 1983
The geometric mean (G.M.) of $k$ positive integers $a_1,a_2,....,a_k$ is defined to be the positive $k$-th root of their product. Show that, the G.M. of a set $S$ of $n$ positive numbers is equal to the G.M. of the G.M.s of all non-empty subsets of $S$.
- Tahmid Hasan
- Posts:665
- Joined:Thu Dec 09, 2010 5:34 pm
- Location:Khulna,Bangladesh.
Re: Canadian MO, 1983
Really cool problem,here's my solution.It's written in a quite clumsy way since I couldn't find the appropriate words.
I hope that you understand.Sorry for the inconvenience.
We'll concentrate on the exponent of each $a_i[1 \le i \le n]$.
Notice that in all the $k$ element sets $a_i$ appears $\binom{n}{k}-\binom{n-1}{k}=\binom{n}{k}\frac{k}{n}$ times.
So the products of $a_i$ for all $k$ element sets will have exponent $\frac{1}{n}\binom{n}{k}$ after the first GM operation.
Because the sets are of $k$ elements,the GM of each $a_i$ will have exponent $\frac{1}{k}$.Then multiplying it with the number of times they appear gives the result.
Then the summation of the exponents of $a_i$ will be $\sum_{k=1}^{n}\frac{1}{n}\binom{n}{k}=\frac{2^n-1}{n}$
[Using the expansion of $(1+1)^n$ and removing the empty set]
since there are $2^n-1$ non-empty subsets, doing the final GM will have exponent $\frac{1}{2^n-1}.\frac{2^n-1}{n}=\frac{1}{n}$
Which is the exponent of $a_i$ in the GM of the mother set.
@Sowmitra-dude, you really have a thing for binomial co-effcients
I hope that you understand.Sorry for the inconvenience.
We'll concentrate on the exponent of each $a_i[1 \le i \le n]$.
Notice that in all the $k$ element sets $a_i$ appears $\binom{n}{k}-\binom{n-1}{k}=\binom{n}{k}\frac{k}{n}$ times.
So the products of $a_i$ for all $k$ element sets will have exponent $\frac{1}{n}\binom{n}{k}$ after the first GM operation.
Because the sets are of $k$ elements,the GM of each $a_i$ will have exponent $\frac{1}{k}$.Then multiplying it with the number of times they appear gives the result.
Then the summation of the exponents of $a_i$ will be $\sum_{k=1}^{n}\frac{1}{n}\binom{n}{k}=\frac{2^n-1}{n}$
[Using the expansion of $(1+1)^n$ and removing the empty set]
since there are $2^n-1$ non-empty subsets, doing the final GM will have exponent $\frac{1}{2^n-1}.\frac{2^n-1}{n}=\frac{1}{n}$
Which is the exponent of $a_i$ in the GM of the mother set.
@Sowmitra-dude, you really have a thing for binomial co-effcients
বড় ভালবাসি তোমায়,মা
Re: Canadian MO, 1983
Nice solution. I think(!) it matches mine. And yes, you were right- it is really tough to find words to formally explain the solution of this problem.
আর ভাই, Combinatorics নিয়ে ঘাটাঘাটি করতে করতে Binomial Co-efficient এর প্রতি আলাদা ভালোবাসা তৈরি হয়ে গেছে।
আর ভাই, Combinatorics নিয়ে ঘাটাঘাটি করতে করতে Binomial Co-efficient এর প্রতি আলাদা ভালোবাসা তৈরি হয়ে গেছে।