頭の体操

Question

『ここに、同種の（見かけは全く同じ）コインが１２枚ある。その中の１枚はニセモノで、重さのみがホンモノと異なっている（重いか軽いかはわからない）。てんびんばかりを３回だけ使って、その中のニセモノを探すにはどうすればいいだろうか。
ただし、てんびんばかりには、ひとつのお皿に何枚コインを乗せてもよい。』
苦戦中です。頭を貸して下さい。

siegmund · Accepted Answer

この問題はここのサイトでも何度か質問がありますが，
決定版は
http://oshiete1.goo.ne.jp/kotaeru.php3?q=30706 
と思います．
任意のコイン数や手順固定などの問題への一般化を含めて
詳細に議論されました．
上のスレッドの内容は学術専門誌に載るのではないかと
思われるレベルです．
もちろん，今までに誰も一般解の類を求めていないとして，
の話ですが．
昔からある(超？)有名な問題ですから，一般化は誰かがやっていても
不思議ではありません．

便乗お願いですが，
この問題の一般化の文献などご存知の方がおられましたら，
ぜひ書き込んでください．

yuusukekyouju · Answer

てんびんばかりをn回だけ使って、その中のニセモノを探すには最大何個まで可能か、その個数をA個とすると
A≦（3＾n+1)/2でなくてはならない。

この原則が成り立つ理由は簡単に説明すると
てんびんはつりあう、右が重い、左が重いの３つの場合しかありません、またコインがA個あったときどれが重いか軽いかは２Aとおりあります。この２Aとおりに対しててんびんのかたむき方はそれぞれ違っていなければいけないので
２A≦３＾ｎとなりますが、一度もてんびんに乗せないコインが重さが異なるときはそれは重いか軽いかわからないので、２A-1≦３＾ｎとなります。

ｎに数字をあてはめる
ｎ＝１の場合Aは２
これは２個のコインがありどちらかがニセモノという場合です。この場合にはこの２個のほかに本物のコインが別になくてはできません。
一方に本物、他方に２個のコインのうちの１個をてんびんにのせる

ｎ＝２の場合Aは５
この場合は１回目は５個のうち片方に２個もう一方に１個それとは別に本物のコインをもう１個乗せる。
つりあえば、乗せていない２個のうち１個がニセモノなので、ｎ＝１の場合と同じになるので、２回目にわかります。
つりあわなければ、２個のせた方のコインを今度はそれぞれ１個ずつ乗せます。つりあえば、最初に乗せた３個のうち２回目に乗せなかったコインがニセモノ、つりあわなければ、２個のうちどちらかがニセモノですが１回目その２個のなかのニセモノは重いか軽いかわかっているので２回目の結果でわかります。

ｎ＝３の場合Aは１４
この場合も１４個のコイン以外に本物が別にあれば１４個まで本物かニセモノか区別がつきます。
説明は省略しますが、

質問の１２枚について、１回目に左右のてんびんに何枚ずつか乗せます、このときつりあえば乗せなかったコインの中にニセモノがあり、残り２回で見つけなければならないので、前に説明したことを参考にすれば、残りは５枚以内でなくてはならない、はじめは左右同じ数乗せるので、４枚ずつ以上乗せなくてはいけない、また５枚ずつ乗せると、両方のてんびんに乗せた１０枚のうちにニセモノがある場合、残り２回のてんびんの傾き方は３＾２で９通りしかないので、判定できません。ですから最初は４枚ずつ乗せるしかありません。

そしてつりあった場合は、簡単にできますね。
ですから、つりあわなかった場合つまり８枚のうちのどれかがニセモノの場合です。
この場合の２回目の乗せ方のヒントです。
１回目に乗せた８個のうち２回目に４個乗せないとした場合その中にニセモノがあった場合残り１回で見つけることは出来ません、でも３個なら見つけることができます。
２回目は１回目に乗せた８個のうち５個を左右振り分けのせます、またこれでは奇数になるので１回めに乗せなかったコインも一部乗せます。
ここから先は考えてください。
わからないときはまた回答します。

TK0318 · Answer

文章で書くと

http://k.excite.co.jp/hp/u/kaitoutom/?pid=0006&showtree=true

図で書くと

http://www.torito.co.jp/puzzles/128_b.html

ということです。

手で動かしてやりたい場合は

http://128.121.222.29/kumamoto/dekiru/coin/coin.htm

有名な問題ですので検索すれば山ほど出ます。

参考URL：http://k.excite.co.jp/hp/u/kaitoutom/?pid=0006&showtree=true,http://www.torito.co.jp/puzzles/128_b.html

頭の体操

この問題はここのサイトでも何度か質問がありますが，

てんびんばかりをn回だけ使って、その中のニセモノを探すには最大何個まで可能か、その個数をA個とすると

文章で書くと

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング