偽物探し

偽物探し

12個の玉がある。
その中に１つだけ偽物がまじっている。
偽物は本物より少しだけ重さが違うことがわかっているが、
本物より重いか軽いかわかっていない。
天秤を３回使って偽物を見つけ出し、
本物よりも重いか軽いかも判断したいのだが、

あらかじめ３回に比べる玉を決めなくてはいけないもの
（つまり、１回目の結果を２回目の測定に生かせない）
とすると、どのように比べたらいいのでしょうか、、？

No.4 ベストアンサー 回答者： Chitano 回答日時： 2010/07/07 14:36

まず、12個の玉にナンバーをつけさせていただきたいです。

1から12にしましょう。
それから、3回の測定を順番に示します。
1回目は：1 2 3 8 VS 4 5 6 7
2回目は：1 2 6 7 VS 8 9 10 11
3回目は：3 5 11 12 VS 2 6 8 9

後、毎回の結果を数字に変換します。左のほうが重いと0、右のほうが重いと2、両方とも同じだと1にします。三つの数字を一回目から三回目まで並べます。その3桁の数を三進数と見なします。もしその数は十二よりも大きいなら、（27-その数）番の玉がにせものです。十二より小さい場合は、その数と同じナンバーの玉がにせものです。

例えば、結果は順番に「左が重い」、「右が重い」、「左が重い」なら、三進数の020になって、6です。
「右が重い」、「左が重い」、「右が重い」なら、三進数の202になって、21になりますが、12より大きいので（27-21）すなわち6にします。

にせものを見出したら、結果に合わせるように本物より重いか軽いかを判断できます。判断しやすいと思います。

ちなみに、この仕方の原理は三進法です。

この回答へのお礼

ありがとうございます！
すごくよく理解できました☆

お礼日時：2010/07/08 15:10

No.6 回答者： Tacosan 回答日時： 2010/07/08 12:04

天秤を使うと, 可能性が「右の方が重い」「左の方が重い」「同じ」の 3通りに分かれるので対数の底を 2 とするのはおかしいし, さらに言えば「n個の硬貨のうち偽物は 1つだけ, ただし本物より重いか軽いかは不明」という状況では可能性として 2n通り考えなきゃいけないので真数もおかしい＞#5.

も～っというと, ceil(log_3 (2n)) で与えられるのは「少なくともこれだけは必要」という回数であって「これだけあれば十分」という回数ではなかったりする.

No.5 回答者： noname#116057 回答日時： 2010/07/07 17:22

　n(＞3)個の玉があって，その中に1個だけ偽物（本物より重いか軽いかは不明）が混じっているとき，偽物を見つけ出すのに必要な天秤の使用回数は，

　log[2]nの小数部を切り上げた数
であることが知られています。
　本問の場合，n＝12なので，
　log[2]12＝3.5・・・
となり，3回では必ずしも偽物を見つけ出すことはできません。

No.3 回答者： kentarou2333 回答日時： 2010/07/07 13:38

球を、A,B,C,D,E,F,G,H,I,J,K,L とすると、

一回目に、(ABCD)と(EFGH)を乗せて、IJKL は乗せない。
二回目に、(ABEF)と(CGIJ)を乗せて、DHKL は乗せない。
三回目に、(AEIK)と(BDFH)を乗せて、CGJL は乗せない。

とやると、A～K が偽物の場合、どれが偽物かと、
偽物が重いのか、軽いのかまで分かります。

ただ、L が偽物の場合、重いのか軽いのかは分かりません。

すいませんが、私にはこれが限界でした。

この回答へのお礼

回答ありがとうございます！
Chitanoさんの回答が正しいようです。

お礼日時：2010/07/08 15:14

No.2 回答者： 9der-qder 回答日時： 2010/07/07 12:24

> つまり、１回目の結果を２回目の測定に生かせない

これじゃ、３回計る意味なくないですか？

No.1 回答者： genedoor 回答日時： 2010/07/07 12:22

<あらかじめ３回に比べる玉を決めなくてはいけないもの

この条件じゃちと無理があるかと＾＾；