Author |
Topic: Biased Weighing (Read 951 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Biased Weighing
« on: Nov 18th, 2011, 1:23am » |
 Quote  Modify
|
Let n > 0 be an integer. We are given a balance and n weights of weight 1, 2, . . . , 2n-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.
Source: IMO 2011.
|
|
 IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Biased Weighing
« Reply #1 on: Nov 18th, 2011, 7:25am » |
Quote Modify
|
Looks like ( 2n - 1 ) !! .
| hidden: | Call the answer an. It is clear that placing 1, 2, ..., 2n-1 is equivalent to placing 2, 4, ..., 2n. So, if there are n weights to be placed, the n-1 largest weights can be placed in an-1 ways. In each of these cases, the weight 1 can be added by placing it either first (only left) or 2nd, 3rd, ..., n-th (in each case, either left or right), for 2n-1 total possibilities. Because the weights are powers of two, the weight 1 cannot have any impact on the options for placing the others.
So we get an = (2n-1) an-1 with a1 = 1, which is trivially equivalent to an = (2n-1)!!. |
Is this really from IMO 2011? Because it seems a little, well, easy...
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Biased Weighing
« Reply #2 on: Nov 18th, 2011, 7:30am » |
Quote Modify
|
If ai is the number of ways of doing this when n=i, then
a0 = 1
an = SUMi=1n { n-1Ci-1 * ai-1 * (n-i)! * 2n-i }
Anyone want to find a closed form?
Derivation:
| hidden: | With the set of weights specified, the "right never heavier" condition is equivalent to saying that a weight can only be placed on the right if it is not the heaviest yet placed. This also holds true for any set of weights where each weight is heavier than all the lighter ones combined.
If the largest weight is the i'th weight placed, then the remaining n-i weights can be placed in any order, and each can be placed on either side. The i-1 weights placed before the heaviest can be any combination of the other n-1 weights, placed in any of the ai-1 ways of placing the first i-1 weights.
Multiplying those factors together gives you the number of ways of placing the n weights with the heaviest i'th. Summing those gives you the number of ways of placing them with the heaviest weight in any position. |
|
| « Last Edit: Nov 18th, 2011, 7:30am by rmsgrey » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Biased Weighing
« Reply #3 on: Nov 18th, 2011, 7:37am » |
Quote Modify
|
on Nov 18th, 2011, 7:25am, pex wrote:| Is this really from IMO 2011? Because it seems a little, well, easy... |
|
And yet...
I believe Olympiads like to include at least one easier question to allow people to settle in and build confidence...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print