第4問

n>0

を整数とする。天秤と、重さが

2^0,2^1,\dots,2^{n-1}

である

n

個のおもりが与えられている。

n

個のおもりを一つずつ天秤に載せていくとき、右の皿が左の皿より重くなることが決してないようにしたい。各段階で、まだ載せていないおもりを一つ選び、左の皿か右の皿のいずれかに載せる操作を、すべてのおもりを載せ終わるまで続ける。このような載せ方の総数を求めよ。

ステップ 2/5: 2 のべき乗はそれより小さいべき乗すべての合計より常に重い

前のステップ次のステップ

ざっくり言うと

$1+2+\cdots+2^{k-1}=2^k-1$ なので、新たに現れた最大記録の重りは、それより小さいものすべてを合わせたより常に重く、自分の乗った皿を必ず重い方にする。

2^k>2^0+2^1+\cdots+2^{k-1}

詳しい解説

任意の $k$ に対して $2^k>2^0+2^1+\cdots+2^{k-1}$ が成り立つ。左辺は $2^k$ に等しく、右辺は telescoping により $2^k-1$ になるからである。したがって、重り $2^k$ が置かれてそれまでの最大記録になった瞬間、それ以前に置かれた（必ずより小さい）重りの合計の絶対値は高々 $2^k-1<2^k$ である。もし $2^k$ が右皿に置かれれば、右皿は左皿を厳密に上回ってしまい禁止される。よって、ある重りが新たな最大記録になる瞬間には、必ず左皿に置かれなければならない。