Sacred Right Pan - IMO 2011 Problem
Source: IMO 2011 Problem (sent to me by Dinesh Dharme, CSE IITB 2011 Alumnus, Credit Suisse Analyst)
Problem:
Let n > 0 be an integer. We are given a balance and n weights of weight 2^0, 2^1, . . . , 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.
Disclaimer:
As expected from an IMO problem, very difficult! But interesting solutions at www.math.leidenuniv.nl/~desmit/pop/2011_imo_final6.pdf
Update (25 Aug 2011):
I did not write in clearly in the post. One of the solutions provided in the pdf is an oral 3 line solution to the problem. It cannot get smaller than this :P. Even if you have solved the problem, do have a look at the pdf
Problem:
Let n > 0 be an integer. We are given a balance and n weights of weight 2^0, 2^1, . . . , 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.
Disclaimer:
As expected from an IMO problem, very difficult! But interesting solutions at www.math.leidenuniv.nl/~desmit/pop/2011_imo_final6.pdf
Update (25 Aug 2011):
I did not write in clearly in the post. One of the solutions provided in the pdf is an oral 3 line solution to the problem. It cannot get smaller than this :P. Even if you have solved the problem, do have a look at the pdf
Biggest weight always goes to left pan, irrespective of when it is placed on pan.
ReplyDeleteThis is because: 1+2+2^2+...+2^n-1 <2^n
Let T(n) be the total number of ways of placing n weights on pan such that left pan is always heavier than the right.
Now we can think recursively, first fixing the position of nth (i.e. largest) weight.
If the nth weight is placed in rth step, then we have to place (r-1) weights before that and (n-r) weights after that.
Placing (r-1) weights can be done in T(r-1) ways:
Because given a set of weights of powers of 2, number of valid ways given an order of placement depends only on order, not on actual weights.
The remaining (n-r) weights can be placed in 2^(n-r) ways.
So, now T(n) = T(n-1)+2T(n-2)+2^2T(n-3)+...+2^(n-1)T(0)
with T(0)=1
Call the RHS as S(n)
Now, 2*S(n)+T(n) = T(n+1)
=> 3T(n) = T(n+1)
with T(1) = 1
Hence, T(n) = 3^(n-1)
Sorry, I guess I got it wrong...
ReplyDeleteYes. You can have a look at the pdf link in the post.
ReplyDelete