MathLabs

第4题

设 n>0n>0 为整数。现有一架天平和 nn 个重量分别为 20,21,…,2n−12^0,2^1,\dots,2^{n-1} 的砝码。我们要依次把这 nn 个砝码放到天平上，使得右盘始终不比左盘重。每一步都从尚未放置的砝码中选一个，放到左盘或右盘上，直到所有砝码都放置完毕。求这样做的方式数。
第 3/5 步：当前差值永远不会低于正在使用的最小砝码
上一步下一步
通俗地说

当前记录砝码落到左盘之后，两侧已放置的更小砝码最多只能削减掉它们的总和，仍会剩下至少最小砝码那么多的余量。

left−right≥2p\text{left}-\text{right}\ge2^p
详细分析

考虑由连续的一段 2p,2p+1,…,2q2^p,2^{p+1},\dots,2^{q} 组成的砝码，观察第一个砝码放置之后的任意时刻。设 2k2^k 为目前放置过的最大砝码，由上一步它落在左盘。其余已放置的砝码都属于 2p,…,2k−12^p,\dots,2^{k-1}，其总和为 2k−2p2^k-2^p，因此它们对 left−right\text{left}-\text{right} 的带符号贡献绝对值至多为 2k−2p2^k-2^p。再加上记录砝码自身的贡献 2k2^k，就得到 left−right≥2p\text{left}-\text{right}\ge2^p，即差值永远不会低于该段中最小的砝码 2p2^p。