IMO 2011 · Problem 4

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

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{1\cdot3\cdot5\cdots(2n-1)=\frac{(2n)!}{2^n n!}}. \]

Solution

Call a sequence of placements valid if the right pan is never heavier than the left pan, and let \(a_n\) be the number of valid sequences.

First observe that, whenever the balance is nonempty, the pan containing the largest weight placed so far is strictly heavier. Indeed, if that weight is \(2^k\), the sum of all smaller weights is \[ 1+2+\cdots+2^{k-1}=2^k-1<2^k, \] where the sum is empty when \(k=0\). Thus a sequence is valid if and only if, at every nonempty stage, the largest weight present lies on the left pan.

We will prove that, for \(n\ge2\), \[ a_n=(2n-1)a_{n-1}. \]

Take any valid sequence for the \(n\) weights and delete the placement of the smallest weight, \(1\). The resulting sequence for \(2,4,\ldots,2^{n-1}\) is valid: at every nonempty stage, its largest weight was also the largest weight at the corresponding stage of the original sequence, so it lies on the left. Dividing every remaining weight by \(2\) gives a valid sequence counted by \(a_{n-1}\).

Conversely, take any sequence counted by \(a_{n-1}\) and double all its weights. This gives a valid sequence of \(n-1\) placements using \(2,4,\ldots,2^{n-1}\). There are exactly \(n\) positions in which to insert the placement of weight \(1\): before the first placement, between consecutive placements, or after the last.

  • If \(1\) is inserted before the first placement, it must go on the left. This choice is valid, since every subsequent stage has the same largest weight as the corresponding stage of the doubled sequence.
  • In any of the other \(n-1\) positions, \(1\) may go on either pan. A larger weight is already present, so inserting \(1\) never changes which weight is largest. The sequence therefore remains valid.

Hence each sequence counted by \(a_{n-1}\) produces exactly \[ 1+2(n-1)=2n-1 \] valid sequences. The construction is reversible by deleting \(1\) and halving the other weights, so no sequence is missed or counted twice. This proves the recurrence.

Finally, \(a_1=1\), since the sole weight must go on the left. Therefore \[ a_n=\prod_{j=1}^{n}(2j-1) =\frac{(2n)!}{2^n n!}. \]

The solution was checked against the official IMO shortlist solutions.