数学）天秤と宝石の問題。

質問

100個の宝石の中に2枚だけ重さの違う偽物がある。正確な天秤を使って偽物を見つけ出す場合、天秤を使う回数は最低で何回か。

この問題はどのように解くのでしょうか。

回答No.6

asuncion

ああ、そうですね。2つ見つけるんだから2倍でした。

回答No.5

asuncion

＞「偽物が混ざっているB」の群が放置されています
A10個と同じ手順を踏めばよいです。

回答No.4

asuncion

天秤を1回使うごとに調べる個数がおよそ半分になっていく、という理屈です（二分法）。

補足

となるとAの分の「最大5回」と
Bの分の「最大5回」を合わせた10回が
最低何回必要か、という答えになるのでしょうか。

回答No.3

asuncion

では、偽物は本物よりも重い、という前提で話を進めます。
100個は数が多いので、20個で考えてみましょう。
1)20個を10個ずつ、AとBに分ける。
2)A10個とB10個を、天秤の左右に乗せる（天秤の1回目）。このとき、
　　・つり合えば、A10個に1個、B10個に1個、偽物がある。 ... (a)
　　・つり合わなかったら、重い方の皿に偽物が2個ある。簡単のために、A10個に2個偽物があるとする。 ... (b)
3)a)のとき、A10個を5個ずつCとDに分けて、天秤の左右に乗せる（天秤の2回目）。このとき、左右どちらかに偽物があるので、つり合わない。
簡単のためにC5個の方が重い（偽物がある）とする。C5個から4個を取り出し、E4個とする。
E4個を2個ずつFとGに分けて、天秤の左右に乗せる（天秤の3回目）。このとき、つり合えば、FにとGに入れなかった分が偽物。つり合わなければ、重い方の皿の2個を比べ、重い方が偽物（天秤の4回目）。ここまででa)の処理は終了。
4)b)のとき、A10個に偽物が2個あることになる。A10個を5個ずつHとIに分けて、天秤の左右に乗せる（天秤の2回目）。このとき、つり合えば、Hに1個、Iに1個の偽物がある。 ...(c)
つり合わなければ、重い方の皿に偽物が2個あることになる。簡単のため、H5個に2個の偽物があるとする。 ...(d)
5)c)のとき、H5個から4個を取り出し、J2個とK2個とし、天秤の左右に乗せる（天秤の3回目）。つり合えば、JとKに入れなかった1個が偽物。つり合わなければ、重い方（簡単のためにJが重いとする）を1個ずつ天秤の左右に乗せ（天秤の4回目）、重い方が偽物。
6)c)のとき、I5個から偽物を見つける方法は5)と同じ。最大4回で偽物が見つかる。
7)d)のとき、H5個（偽物が2個ある）から4個を取り出し、L2個とM2個にし、天秤の左右に乗せる（天秤の3回目）。つり合えば、L2個のうち1個が、かつ、M2個のうち1個がそれぞれ偽物。
L2個とM2個をそれぞれ比べればよいから、あと2回（つまり合計5回）で2個の偽物が見つかる。
3回目でつり合わなければ、L2個、M2個に入れなかった残りが1個目の偽物。2個目を見つける際、簡単のために、L2個の方が重いとする。L2個を1個ずつに分けて天秤の左右に乗せる（天秤の4回目）。重い方が2個目の偽物。

以上の考察により、宝石が20個の場合は最大5回で2個の偽物が見つかる。
log[2]20 ≒ 4.32より、うまくいけば4回、最大でも5回で見つかる。
100個に拡張すると、log[2]100 ≒ 6.64より、うまくいけば6回、最大でも7回でで見つかる。

補足

途中から「偽物が混ざっているB」の群が放置されていますが、「Bに混ざっている偽物を発見する手順」はなぜカットしても良いのでしょうか...？

回答No.2

asuncion

＞どちらかに重い宝石が乗っているか
おや？問題の内容がいつの間にか変わってますね。

＞2枚だけ重さの違う偽物
偽物は本物よりも重い、は前提としてわかっているのですか？

補足

前提です。

50個ずつに分けて天秤に乗せると

・釣り合う
・片方だけが傾く

のどちらかになるのはわかりますが
ここからあまりにも膨大な分岐をするため
わけが分からなくなりました。

回答No.1

asuncion

問題のサイズを小さくして、20個の宝石について考えてみたらどうでしょう。
例えば、10個ずつ左右の皿に乗せて重さを量ったとき、
つり合えば左右に1個ずつある。
つり合わなかったら、左右いずれかを5個ずつに分けて量る。
つり合えば…
つり合わなかったら…

という風に絞れていくのではないかと思います。

補足

そこが疑問で、「2つ宝石があり、天秤のどちらかに重い宝石が乗っているかわからない」のに
なぜ「天秤を最低何回使うか」という完全不確定な答えを求めることが可能なのかが理解できないのです。