IMO 2011 Problem 4

Discussion on International Mathematical Olympiad (IMO)
User avatar
Moon
Site Admin
Posts:751
Joined:Tue Nov 02, 2010 7:52 pm
Location:Dhaka, Bangladesh
Contact:
IMO 2011 Problem 4

Unread post by Moon » Wed Jul 20, 2011 12:33 pm

Let $n > 0$ be an integer. We are given a balance and $n$ weights of weight $2^0, 2^1, \cdots, 2^{n-1}$. We are to place each of the $n$ weights on the balance, one after another, in such a way that the right pan is never heavier than the left pan. At each step we choose one of the weights that has not yet been placed on the balance, and place it on either the left pan or the right pan, until all of the weights have been placed.
Determine the number of ways in which this can be done.
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin

Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh

Re: IMO 2011 Problem 4

Unread post by Masum » Fri Jul 22, 2011 11:28 pm

Moon wrote:Let $n > 0$ be an integer. We are given a balance and $n$ weights of weight $2^0, 2^1, \cdots, 2^{n-1}$. We are to place each of the $n$ weights on the balance, one after another, in such a way that the right pan is never heavier than the left pan. At each step we choose one of the weights that has not yet been placed on the balance, and place it on either the left pan or the right pan, until all of the weights have been placed.
Determine the number of ways in which this can be done.
Let the number of ways be $\pi(n)$.
The answer is $\pi(n)=1.3.5....(2n-1)$.
We will prove it by induction.
It is trivially true for $n=1,3$.
Now think to set $n+1$ weights.
Now while considering their setup, note that since $2^n>2^{n-1}+.......+2+1$ we must set the weight $2^n$ in left. In this case we have the previous $\pi(n)$ ways associated.
For $k<n,2^k$ can be set in left or right. And we may choose one of the $n$ weights in one side. So the number of ways will be multiplied by $2n$ with $\pi(n)$ since for any choice of a weight we have $\pi(n)$ ways.
Thus $\pi(n+1)=2n\pi(n)+\pi(n)=(2n+1)\pi(n)=1.3.....(2n+1)$
One one thing is neutral in the universe, that is $0$.

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh

Re: IMO 2011 Problem 4

Unread post by Masum » Fri Jul 22, 2011 11:28 pm

This is the first problem in Combinatorics I have ever solved from Imo.
One one thing is neutral in the universe, that is $0$.

Post Reply