第4题

设

n>0

为整数。现有一架天平和

n

个重量分别为

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

的砝码。我们要依次把这

n

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

第 4/5 步：把最小砝码恰好用 2n-1 种方式插回

上一步下一步

通俗地说

把有效的 n-1 个砝码顺序整体加倍后仍然有效，且此后任何阶段都至少留有 2 的余量，因此微小的砝码 1 几乎可以插在任何地方而不破坏平衡，唯独它自己的第一步没有选择余地。

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

详细分析

任取 $n-1$ 个砝码 $2^0,\dots,2^{n-2}$ 的一个有效顺序，把所有砝码加倍，得到 $2^1,\dots,2^{n-1}$ 的一个有效顺序（加倍保持所有大小比较）。由上一步取 $p=1$ 可知，从第一步起其当前差值始终至少为 $2$ 。现在插入缺失的砝码 $2^0=1$ ：插在第一步之前只能放左边（否则右盘已经超过左盘），有 $1$ 种方式；插在已有 $n-1$ 步中任意一步之后，左右两盘都可以放，因为至少为 $2$ 的余量足以吸收多出来的 $1$ ，这又给出 $2(n-1)$ 种方式。总共恰好有 $1+2(n-1)=2n-1$ 种有效插入方式，而撤销一次插入正是第一步中的遗忘映射，因此这给出了从有效的 $n$ 个砝码顺序到有效的 $n-1$ 个砝码顺序之间的 $(2n-1)$ 对 $1$ 对应。