中学数学をなめてはいけないなぁ・・・

質問

12個のおもりがあって、そのうち１つだけ重さの違うおもりがまぎれています。
それを、てんびんを３回だけ使って見分ける方法を教えてください。
ただし、重さの違うおもりは他のおもりより重いか軽いかわかりません。
わかった方は至急おしえてください。おねがいします。

回答No.9

punchan_jp

n個のおもりがあって少しだけ重さの違うものが確実に1個まぎれて
いる場合、それぞれのおもりをちゃんと区別できるなら 2n 通りの
場合が存在します。通常はそれらの確率は等しいとできますので、
この状況が持つ平均情報量は log_2 (2n) ビットと表せます。

これに対して、天秤でおもりを同数ずつ乗せた場合、左に傾くか、
右に傾くか、つりあうかの3通りの場合があります。それぞれの場
合を構成する場合の数を等しくできるならば、つまり、1回計るこ
とによって、可能性を正確に1/3に限定できるように分けられるな
ら、log_2 3 ビットだけの情報量が得られます。

つまり、理想的な分け方ができる限り、
ceiling(log_2 (2n) / log_2 3) = ceiling(log_3 (2n)) 回で重さ
の違うおもりを見分けられることがわかります。これが回数の理論
的な下限といえます。（ceiling は切り上げの意）

n=14では、この値は4になりますので、3回では不可能であることが
証明されます。n=40でも4なので、もしうまい分け方があれば4回で
検出できますが、それは情報量の観点のみからでは保証されません。