第4题

设

n>0

为整数。现有一架天平和

n

个重量分别为

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

的砝码。我们要依次把这

n

个砝码放到天平上，使得右盘始终不比左盘重。每一步都从尚未放置的砝码中选一个，放到左盘或右盘上，直到所有砝码都放置完毕。求这样做的方式数。

第 2/5 步：任何一个 2 的幂总是超过所有更小幂之和

上一步下一步

通俗地说

由于 $1+2+\cdots+2^{k-1}=2^k-1$ ，新出现的最大砝码总是比它之前所有更小砝码加起来还重，因此会迫使它所在的一侧成为更重的一侧。

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

详细分析

对任意 $k$ ， $2^k>2^0+2^1+\cdots+2^{k-1}$ 成立，因为左边等于 $2^k$ ，右边逐项相消后等于 $2^k-1$ 。因此，当砝码 $2^k$ 被放置并成为目前为止最大的砝码时，之前放置的（必然更小的）所有砝码之和的绝对值至多为 $2^k-1<2^k$ ；若 $2^k$ 被放到右盘，右盘就会严格超过左盘，这是不允许的。因此每个砝码在成为新的最大记录时，都必须被放在左盘。