問題. (偽金貨問題)
$N$ 枚の金貨のうち $1$ 枚が重さの異なる偽物である. 天秤を何回使えば判別可能か？
$n$ 枚目の金貨が重いという結果を $n _ +$, 軽いという結果を $n _ -$, 等しいという結果を $0$ と表すとき, 確率空間は $\Omega=\lbrace 0,1 _ +,1 _ -,\dots,N _ +,N _ -\rbrace$ となり, どれも等確率なのでエントロピーは $\log _ {2}(2N+1)$ である. 一回天秤を使うと「左が重い」「右が重い」「どちらも同じ」の情報が得られるため, 少なくとも $\log _ 2{3}$ だけエントロピーが減少する. したがって少なくとも $$\left\lceil\frac{\log_{2}(2N+1)}{\log_2{3}}\right\rceil$$ 回の操作が必要である. 実際にこの回数で判別できるかどうかは各ステップを具体的に構成しなければならないが, どの可能性においてもエントロピーが $\log _ 2{3}$ に残りの測定回数を掛けたものを超えないようにすること, つまり残される可能性が $3 ^ \text{(残りの測定回数)}$ を超えないようにすることに注意すればよい.
