MathLabs

第4問

n>0n>0 を整数とする。天秤と、重さが 20,21,…,2n−12^0,2^1,\dots,2^{n-1} である nn 個のおもりが与えられている。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}
詳しい解説

nn 個の重り 20,21,…,2n−12^0,2^1,\dots,2^{n-1} の有効な配置順の個数を f(n)f(n) とし、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} に対する有効な配置が得られる。