|
||
Title: Biased Weighing Post by Barukh on Nov 18th, 2011, 1:23am 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: [hide]IMO 2011[/hide]. |
||
Title: Re: Biased Weighing Post by pex on Nov 18th, 2011, 7:25am Looks like [hide] ( 2n - 1 ) !! [/hide]. [hideb]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)!!.[/hideb] Is this really from [hide]IMO 2011[/hide]? Because it seems a little, well, easy... |
||
Title: Re: Biased Weighing Post by rmsgrey on Nov 18th, 2011, 7:30am 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: [hideb]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.[/hideb] |
||
Title: Re: Biased Weighing Post by rmsgrey on Nov 18th, 2011, 7:37am on 11/18/11 at 07:25:55, pex wrote:
And yet... I believe Olympiads like to include at least one easier question to allow people to settle in and build confidence... |
||
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |