Problem 4

Let

n>0

be an integer. We are given a balance and

n

weights of weight

2^0,2^1,\dots,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.

Step 1 of 5: Set up a forgetful map between consecutive sizes

Previous step Next step

In plain words

The weight 1 need not be first. Delete its move; if it was on the right, the earlier imbalance was an even positive amount, so halving the other weights keeps the left pan at least as heavy.

2^0,2^1,\dots,2^{n-1}\ \to\ 2^0,2^1,\dots,2^{n-2}

Detailed analysis

Let $f(n)$ be the number of valid placement orders for the $n$ weights $2^0,2^1,\dots,2^{n-1}$ ; we aim to show $f(n)=1\cdot3\cdot5\cdots(2n-1)=(2n-1)!!$ . The base case $f(1)=1$ is immediate: with only the weight $1$ , placing it on the right would already make the right pan heavier, so it must go on the left, giving exactly one valid order. Given any valid order for $n$ weights, delete the single move that places weight $2^0$ and halve every remaining weight; a short check shows the right pan is still never heavier than the left at any stage, so this produces a valid order for the $n-1$ weights $2^0,\dots,2^{n-2}$ .