wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Biased Weighing
        
(Message started by: Barukh on Nov 18^th, 2011, 1:23am)

Title: Biased Weighing
Post by Barukh on Nov 18^th, 2011, 1:23am

Let n > 0 be an integer. We are given a balance and n weights of weight 1, 2, . . . , 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.

Source: [hide]IMO 2011[/hide].

Title: Re: Biased Weighing
Post by pex on Nov 18^th, 2011, 7:25am

Looks like [hide] ( 2n - 1 ) !! [/hide].

[hideb]Call the answer a_n. It is clear that placing 1, 2, ..., 2^n-1 is equivalent to placing 2, 4, ..., 2ⁿ. So, if there are n weights to be placed, the n-1 largest weights can be placed in a_n-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 a_n = (2n-1) a_n-1 with a₁ = 1, which is trivially equivalent to a_n = (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 18^th, 2011, 7:30am

If a_i is the number of ways of doing this when n=i, then

a₀ = 1
a_n = SUM_i=1ⁿ { ^n-1C_i-1 * a_i-1 * (n-i)! * 2^n-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 a_i-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 18^th, 2011, 7:37am

on 11/18/11 at 07:25:55, pex wrote:

Is this really from [hide]IMO 2011[/hide]? 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...