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 4 of 5: Insert the smallest weight back in exactly 2n-1 ways

Previous step Next step

In plain words

Doubling a valid (n-1)-weight order keeps it valid and leaves a safety margin of at least 2 at every later stage, so the tiny weight 1 can be slipped in almost anywhere without upsetting the balance, except that it has no choice on its very first move.

1+2(n-1)=2n-1

Detailed analysis

Take any valid order for the $n-1$ weights $2^0,\dots,2^{n-2}$ and double every weight, giving a valid order for $2^1,\dots,2^{n-1}$ (doubling preserves every comparison). By the previous step with $p=1$ , its running difference is at least $2$ from the first move onward. Now insert the missing weight $2^0=1$ : placed before the very first move it must go on the left (right would already exceed left), giving $1$ way; inserted after any of the $n-1$ existing moves it can go on either pan without ever making the right pan heavier, since the margin of at least $2$ absorbs the extra $1$ , giving $2(n-1)$ more ways. In total there are exactly $1+2(n-1)=2n-1$ valid insertions, and undoing an insertion is exactly the forgetful map of the first step, so this exhibits a $(2n-1)$ -to- $1$ correspondence from valid $n$ -weight orders onto valid $n-1$ -weight orders.