2011 IMO Problems/Problem 4

Problem

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.

Solution

Call our answer $W(n)$ . We proceed to prove $W(n)=(2n-1)!!$ .

It is evident $W(1)=1$ .

Now, the key observation is that smaller weight can never add up to the weight of a larger weight, ie which side is heavier is determined completely by the heaviest weight currently placed. It follows, therefore, that the number of ways to place $n$ weights on the balance according to the rule is the same no matter which $n$ distinct powers of two are the weights, as each weight completely overpowers any smaller weight and is completely overpowered by any larger weight. That is, there is the 1st heaviest weight, the 2nd heaviest, the 3rd, ..., the n-th heaviest, and each weight is negligible compared to any heavier weight. Thus, any valid placement of $n$ weights of weight $2^0,2^1, \cdots ,2^{n-1}$ can changed by replacing $2^i$ with the $(n-i)$ -th heaviest weight in the set ${2^{a_k}}$ , where $a_k \in \mathbb{Z}$ , and vice versa, forming a $1:1$ relation. With this in mind, we do casework upon the last weight placement. There are $2n-1$ choices; namely, you can put any weight on either side except for the heaviest weight on the right. For the first $n-1$ weight placements, the answer reduces to $W(n-1)$ . We can reduce $W(n-1)$ in the same way.

$W(n)=(2n-1)W(n-1)=(2n-1)(2n-3)W(n-2)=...=(2n-1)!!W(1)=(2n-1)!!$

$\text{QED}$

Page

Toolbox

Search

2011 IMO Problems/Problem 4

Problem

Solution