MathLabs

第4問

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