MathLabs

第4题

设 n>0n>0 为整数。现有一架天平和 nn 个重量分别为 20,21,…,2n−12^0,2^1,\dots,2^{n-1} 的砝码。我们要依次把这 nn 个砝码放到天平上，使得右盘始终不比左盘重。每一步都从尚未放置的砝码中选一个，放到左盘或右盘上，直到所有砝码都放置完毕。求这样做的方式数。
第 1/5 步：在相邻两个规模之间设立一个遗忘映射
上一步下一步
通俗地说

砝码 1 不必最先放置。删去放置它的步骤；若它放在右盘，则此前的差是正偶数，把其余砝码减半后左盘仍不轻。

20,21,…,2n−1 → 20,21,…,2n−22^0,2^1,\dots,2^{n-1}\ \to\ 2^0,2^1,\dots,2^{n-2}
详细分析

设 f(n)f(n) 为 nn 个砝码 20,21,…,2n−12^0,2^1,\dots,2^{n-1} 的有效放置顺序数，我们要证明 f(n)=1⋅3⋅5⋯(2n−1)=(2n−1)!!f(n)=1\cdot3\cdot5\cdots(2n-1)=(2n-1)!!。基本情形 f(1)=1f(1)=1 是显然的：只有砝码 11 时，放在右边会立刻使右盘更重，故只能放左边，恰有一种有效顺序。对 nn 个砝码的任意有效顺序，删去放置 202^0 的那一步，并把其余每个砝码都减半；简单检验可知右盘在任何阶段仍不会比左盘重，于是就得到 n−1n-1 个砝码 20,…,2n−22^0,\dots,2^{n-2} 的一个有效顺序。