给定整数 $n>0$．有一个天平和 $n$ 个重量分别为 $2^{0},2^{1},\ldots,2^{n-1}$ 的砝码．
现通过 $n$ 步操作逐个将所有砝码都放上天平，使得在操作过程中，右边的重量总不超过左边的重量．每一步操作是从尚未放上天平的砝码中选择一个砝码，将其放到天平的左边或右边，直至所有砝码都被放上天平．
求整个操作过程的不同方法个数．（伊朗）
现通过 $n$ 步操作逐个将所有砝码都放上天平，使得在操作过程中，右边的重量总不超过左边的重量．每一步操作是从尚未放上天平的砝码中选择一个砝码，将其放到天平的左边或右边，直至所有砝码都被放上天平．
求整个操作过程的不同方法个数．（伊朗）
【难度】
【出处】
2011年第52届IMO试题
【标注】
【答案】
略
【解析】
操作过程的不同方法个数为 $(2n-1)!!=1\times 3\times 5\times \cdots\times(2n-1)$．
下面我们对 $n$ 用数学归纳法．
当 $n=1$ 时，只有一个砝码，只要放在天平的左边，故只有 $1$ 种方法．
假设 $n=k$ 时，$k$ 个重量为 $2^0,2^1,\cdots,2^{k-1}$ 的砝码按题设要求有 $(2k-1)!!$ 种方法．
当 $n=k+1$ 时，此时将所有砝码的重量都乘以 $\dfrac{1}{2}$，不影响问题的本质．此时 $k+1$ 个砝码的重量为 $\dfrac{1}{2},1,2,\cdots,2^{k-1}$．由于对任意正整数 $r$，有 $\displaystyle 2^r>2^{r-1}+2^{r-2}+\cdots+1+\dfrac{1}{2}\geqslant \sum\limits_{i=-1}^{r-1}\pm 2^{i}$
所以当所有砝码都放上天平时，天平的较重的一端只取决于天平上最重砝码的位置，故最重砝码一定在左边．下面考虑重量为 $\dfrac{1}{2}$ 的砝码在操作过程中的位置．
（1）若重量为 $\dfrac{1}{2}$ 的砝码在第 $t$ 次操作时放，$t=2,3,\cdots,k+1$．由于此时已经放在天平上的砝码重量均大于 $\dfrac{1}{2}$，所以重量为 $\dfrac{1}{2}$ 的砝码不会成为重要的一个，无论它放左边还是右边都不会影响最重砝码的位置，于是有 $2$ 种放法，而剩下的砝码的放法不受影响，此时有 $2\times (2k-1)!!$ 种放法．
综上所述，当 $n=k+1$ 时，共有
$(2k-1)!!+2k\times (2k-1)!!=(1+2k)(2k-1)!!=(2k+1)!!$ 种放法．
所以，由数学归纳法知，对于任意整数 $n>0$，整个操作过程的不同方法个数为 $(2n-1)!!$．
下面我们对 $n$ 用数学归纳法．
当 $n=1$ 时，只有一个砝码，只要放在天平的左边，故只有 $1$ 种方法．
假设 $n=k$ 时，$k$ 个重量为 $2^0,2^1,\cdots,2^{k-1}$ 的砝码按题设要求有 $(2k-1)!!$ 种方法．
当 $n=k+1$ 时，此时将所有砝码的重量都乘以 $\dfrac{1}{2}$，不影响问题的本质．此时 $k+1$ 个砝码的重量为 $\dfrac{1}{2},1,2,\cdots,2^{k-1}$．由于对任意正整数 $r$，有 $\displaystyle 2^r>2^{r-1}+2^{r-2}+\cdots+1+\dfrac{1}{2}\geqslant \sum\limits_{i=-1}^{r-1}\pm 2^{i}$
所以当所有砝码都放上天平时，天平的较重的一端只取决于天平上最重砝码的位置，故最重砝码一定在左边．下面考虑重量为 $\dfrac{1}{2}$ 的砝码在操作过程中的位置．
（1）若重量为 $\dfrac{1}{2}$ 的砝码在第 $t$ 次操作时放，$t=2,3,\cdots,k+1$．由于此时已经放在天平上的砝码重量均大于 $\dfrac{1}{2}$，所以重量为 $\dfrac{1}{2}$ 的砝码不会成为重要的一个，无论它放左边还是右边都不会影响最重砝码的位置，于是有 $2$ 种放法，而剩下的砝码的放法不受影响，此时有 $2\times (2k-1)!!$ 种放法．
综上所述，当 $n=k+1$ 时，共有
$(2k-1)!!+2k\times (2k-1)!!=(1+2k)(2k-1)!!=(2k+1)!!$ 种放法．
所以，由数学归纳法知，对于任意整数 $n>0$，整个操作过程的不同方法个数为 $(2n-1)!!$．
答案
解析
备注
