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 2 of 5: A power of two always outweighs every smaller one combined

Previous step Next step

In plain words

Because $1+2+\cdots+2^{k-1}=2^k-1$ , the newest record-large weight is always heavier than the pile of everything smaller put together, so it forces its own pan to be the heavy one.

2^k>2^0+2^1+\cdots+2^{k-1}

Detailed analysis

For any $k$ , $2^k>2^0+2^1+\cdots+2^{k-1}$ , since the left side equals $2^k$ and the right side telescopes to $2^k-1$ . Consequently, at the moment when the weight $2^k$ is placed and becomes the largest weight placed so far, the total of all previously placed (necessarily smaller) weights has absolute value at most $2^k-1<2^k$ ; if $2^k$ were placed on the right pan, the right side would then strictly exceed the left, which is forbidden. Hence every weight, at the moment it becomes the new record maximum, must be placed on the left pan.