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 3 of 5: The running difference never drops below the smallest weight in play

Previous step Next step

In plain words

Right after the current record weight lands on the left, all the smaller weights placed on either side can chip away at most the sum of everything below it, which still leaves at least the very smallest weight of margin.

\text{left}-\text{right}\ge2^p

Detailed analysis

Consider weights forming a consecutive block $2^p,2^{p+1},\dots,2^{q}$ , and look at any moment after the first weight has been placed. Let $2^k$ be the largest weight placed so far; by the previous step it sits on the left. All other placed weights are among $2^p,\dots,2^{k-1}$ , whose values sum to $2^k-2^p$ , so their signed contribution to $\text{left}-\text{right}$ has absolute value at most $2^k-2^p$ . Adding the contribution $2^k$ of the record weight itself gives $\text{left}-\text{right}\ge2^p$ , i.e. the difference never falls below the smallest weight $2^p$ of the block.