Canadian MO, 1983

For discussing Olympiad Level Combinatorics problems
User avatar
sowmitra
Posts:155
Joined:Tue Mar 20, 2012 12:55 am
Location:Mirpur, Dhaka, Bangladesh
Canadian MO, 1983

Unread post by sowmitra » Sun Sep 09, 2012 5:57 pm

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$.
"Rhythm is mathematics of the sub-conscious."
Some-Angle Related Problems;

User avatar
Tahmid Hasan
Posts:665
Joined:Thu Dec 09, 2010 5:34 pm
Location:Khulna,Bangladesh.

Re: Canadian MO, 1983

Unread post by Tahmid Hasan » Mon Sep 10, 2012 12:05 am

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 ;)
বড় ভালবাসি তোমায়,মা

User avatar
sowmitra
Posts:155
Joined:Tue Mar 20, 2012 12:55 am
Location:Mirpur, Dhaka, Bangladesh

Re: Canadian MO, 1983

Unread post by sowmitra » Mon Sep 10, 2012 7:26 pm

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 এর প্রতি আলাদা ভালোবাসা তৈরি হয়ে গেছে। :mrgreen:
"Rhythm is mathematics of the sub-conscious."
Some-Angle Related Problems;

Post Reply