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

質問

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

回答No.25

stomachman

うー。どなたも閉めてくださらないようなので、責任とります。

では、一般に(3^(N+1)-1)/2> K > (3^N-1)/2個のおもりの場合の手順を示す問題を片づけます。
この3^N通りの場合についてそれぞれ手順を示す必要があり、これらの場合いずれも少なくとも(N+1)回の計測が必要であることは既に証明されました。
さらに、いずれも(N+1)回の計測で済む、というのがこれから検討する予想です。
方針としては、最初の１回の計測の結果に基づいて、N回天秤を使う場合の定理１～5に帰着してやれば良い。

[A]始めにN=1の場合を考えます。すなわち
4 > K > 1
つまりK=2か３です。
K=2の場合には判定は不可能です。天秤は必ず傾きますが、どっちが異常なのか決められません。
K=3なら定理１で２回で判定可能。
ついでにK=4なら、N=2とした場合の定理５によって、２回で判定可能です。

[B]次にN>1の場合を考えます。
左右の皿にA個づつ乗せて、残りK-2A個を乗せません。このとき、
K-2A = (3^N-1)/2もしくは(3^N-1)/2-1を天秤に乗せないというのが旨いやり方のようです。

一般に(3^(N+1)-1)/2> K > (3^N-1)/2の場合、
最初の１回の計測において、天秤の左右の皿にそれぞれA個(K/2>A>0)のおもりを乗せて、K-2A個は乗せないものとします。ここでK-2A = (3^N-1)/2もしくは(3^N-1)/2-1とします。
(a) 天秤が釣り合った場合
乗せなかったK-2A個のおもりの中に異常なものがある。そして2A個(2A>0)の正常なおもりが手に入りました。そうしたら、調べたいK-2A個のおもりに、必要ならあと１個正常と分かったおもりを加えて(3^N-1)/2個にし（K > (3^N-1)/2だから必ずこれは可能です）、そして
定理5：余分の正常なおもりを借りられなくても、「この中に異常な物が１個ある」と分かっているおもり(3^N-1)/2個（この集合をXとする）の内から、N回の測定で異常なおもりを特定できる。(N≧1)
を使うとN回で計測が可能になります。最初の１回の計測と合わせて(N+1)回で判定できました。

(b)天秤が釣り合わない場合はどうでしょうか。
(3^(N+1)-1)/2> K
です。そして
K-2A = (3^N-1)/2もしくは(3^N-1)/2-1
となるようにしたのですから、
K-2A = (3^N-1)/2　　∴2A=K-(3^N-1)/2<3^N-1　
あるいは
K-2A = (3^N-1)/2-1 ∴2A=K-(3^N-1)/2+1<3^N+1
です。つまりいつでも
A≦(3^N-1)/2、余分の正常なおもりはK-2A ≧(3^N-1)/2-1
となります。
定理3：余分の正常なおもりを借りられるとしたとき、
「この中に重い物はない」と分かっているおもり(3^N-1)/2個（この集合をLとする）と、
「この中に軽い物はない」と分かっているおもり(3^N-1)/2個（この集合をHとする）の中に異常な物が１個ある場合、N回の測定で異常なおもりを特定できる。（N≧1）
を使うためには、
・N>1の場合、余分の正常なおもりが3^(N-1)個必要です。ところがN>1ならば必ず
3^(N-1)≦(3^N-1)/2-1
ですから、正常なおもりが不足する心配はありません。念のために確かめますと
(3^N-1)/2-1-3^(N-1)=3^(N-1)-3/2
ここでN>1より
3^(N-1)≧3
だから、
(3^N-1)/2-1-3^(N-1)＞0
ゆえに
3^(N-1)＜(3^N-1)/2-1
です。
かくて、天秤が釣り合わない場合にもN回で判定が可能であり、最初の１回と合わせて(N+1)回で判定できました。

また、(3^N-1)/2= Kの場合にN回で判定する手順は定理5に示されています。
以上をまとめると、
・K=1個の場合には測定なしで判定できる。
・K=2個の場合には判定が不可能である。
・K=3個の場合には高々２回の計測で判定できる。（定理1参照）
・K=4個の場合には高々２回の計測で判定できる。（定理5参照）
・N>1について、
(3^(N+1)-1)/2> K > (3^N-1)/2の場合には、(N+1)回の計測で判定できる。
その手順は、
左右の皿に同数のおもりをのせて、残りが(3^N-1)/2もしくは(3^N-1)/2-1個になるようにする。
(a)もし釣り合ったら、秤に乗せなかったおもりの数を(3^N-1)/2になるようにし、定理５を適用。
(b)もし釣り合わなかったら、定理３を適用。
です。
K=(3^(N+1)-1)/2の場合には(N+1)回の計測で判定できる。（定理5参照）

以上でこの問題は完全解決を見ました。おめでとう！！