どこかで見た問題

natsu　(2004/04/23(Fri) 01:37:51)

ここに九個のルビーがある。本物は全部同じ重さだが、偽のルビーは本物より軽い（そして、偽のルビー同士は同じ重さです）。
この中に一つ偽のルビーがある場合、天秤を二回使えば偽のルビーを見つけることができます。
では、
（１）この中に２つの偽のルビーがある場合、天秤を何回使えば偽のルビーを見つけることができますか。
（２）この中に偽のルビーがいくつあるかわからない場合、天秤を何回使えば全ての偽のルビーを見つけることができますか。


この記事は削除されました


問題読みましたか？＞シィさん

(２)「全部本物」と「全部偽物」のどちらかの場合、区別がつかないので、
何回天秤を使っても不可能です。


(2)BBQさんのいうとおりですけども、
とりあえず好意的に解釈して、ひとつは偽物があるとしましょう。

ルビーを一列に並べて隣り合うルビー同士を天秤にかければ
どれが偽物か判別できますね。だから8回あれば十分。
7回以下に減らせるのか、どうかが難しい。

(1)9個のうち偽のルビーが2つあるというシチュエーションの場合の数は9*8/2=36。
一回の測定で 大小及び釣り合うの3種類の測定結果があるから
3*3*3 < 36 < 3*3*3*3より すくなくとも4回は測定する必要がある。
＃つまり3回の測定結果では測定結果の場合の数が27しかないから 
＃情報量的に 判別付加ということ。


さて、以下で4回あれば十分であることを示そう。
9個のルビーを３つずつのグループに分け、それぞれのグループをA,B,Cとする。
AとBのグループを天秤にかける。（1回目）
--------------------------------------------------------
１）A=Bのとき：
AとBに1個ずつ偽があるか、Cに偽が２つあるかのどちらか。
Aの３つをA1,A2,A3として、
A1とA2、A2とA3を天秤にかける。（累計3回）
こうすればAの３つについてどれが偽か判別可能。

*)Aがすべて本物のとき
  Bもすべて本物で、Cに偽が２つ。
  Cから２つ選んで天秤にかければ（累計4回） Cのどれが偽か分かる。

*)Aの1個が偽物のとき
  Cはすべて本物で Bに偽が１つ。
  Bから２つ選んで天秤にかければ（累計4回） Bのどれが偽か分かる。
--------------------------------------------------------
２）A<Bのとき
AとCに偽が1個ずつあるか、Aに偽が２つあるかのどちらか
Aの３つについて上記と同様に2回調べてどれが偽か調べる（累計3回）

*)Aの1個が偽物のとき
  Bはすべて本物で、Cに偽が１つ。
  Cから２つ選んで天秤にかければ（累計4回） Cのどれが偽か分かる。

*)Aの2個が偽物のとき
  もちろん BもCも全て本物で 調べることは何も無い。
--------------------------------------------------------
いずれにしても4回あれば十分である。


Q.E.D.

おととさん、どうもありがとう。
でも、実は、ＢＢＱさんの答え（なんかいやってもだめ）が、私の用意した答えでした。
（１）は、おととさん、大正解（４回です）。
（２）で、ひとつは偽物がある場合、どうなるのか考えてみます。


※　問題中に使用されている人名、地域名、会社名、組織名、製品名、イベントなどは架空のものであり、実在に存在するものを示すものではありません。