MathLabs

第4問

n>0n>0 を整数とする。天秤と、重さが 20,21,…,2n−12^0,2^1,\dots,2^{n-1} である nn 個のおもりが与えられている。nn 個のおもりを一つずつ天秤に載せていくとき、右の皿が左の皿より重くなることが決してないようにしたい。各段階で、まだ載せていないおもりを一つ選び、左の皿か右の皿のいずれかに載せる操作を、すべてのおもりを載せ終わるまで続ける。このような載せ方の総数を求めよ。
ステップ 4/5: 最小の重りをちょうど 2n-1 通りに挿入し直す
前のステップ次のステップ
ざっくり言うと

有効な n-1 個の重りの配置を2倍しても有効なままで、その後のどの段階でも少なくとも 2 の余裕が残るので、小さな重り 1 はほとんどどこにでも挿入でき、最初の一手だけは選択肢がない。

1+2(n−1)=2n−11+2(n-1)=2n-1
詳しい解説

n−1n-1 個の重り 20,…,2n−22^0,\dots,2^{n-2} に対する任意の有効な配置を取り、すべての重りを2倍すると、21,…,2n−12^1,\dots,2^{n-1} に対する有効な配置が得られる（2倍してもすべての大小関係は保たれる）。前段より p=1p=1 の場合として、最初の一手以降その時点の差は常に 22 以上である。ここで欠けている重り 20=12^0=1 を挿入する。最初の一手より前に置くなら左しかなく（右がすでに左を上回ってしまう）、これで 11 通り。既存の n−1n-1 手のどれかの後に挿入するなら、少なくとも 22 の余裕が追加の 11 を吸収するので左右どちらでもよく、これで 2(n−1)2(n-1) 通り増える。合計でちょうど 1+2(n−1)=2n−11+2(n-1)=2n-1 通りの有効な挿入があり、挿入を取り消す操作はまさに最初の手順の忘却写像なので、これは有効な nn 個の重りの配置から有効な n−1n-1 個の重りの配置への (2n−1)(2n-1) 対 11 の対応を与える。