日本バックギャモン協会掲示板
http://www.backgammon.gr.jp/forum/

毒入りワインを発見する問題
http://www.backgammon.gr.jp/forum/viewtopic.php?f=2&t=3592
ページ 22

作成者:  すかたろう [ 2014/04/09 02:18 ]
記事の件名:  Re: 毒入りワインを発見する問題

毒の入っていないワインを飲んだ奴隷が、何か他の要因で10~20時間以内に偶然死んでしまうという可能性はないのかな。

作成者:  kinchan [ 2014/04/18 13:06 ]
記事の件名:  Re: 毒入りワインを発見する問題

すかたろう さんが書きました:
毒の入っていないワインを飲んだ奴隷が、何か他の要因で10~20時間以内に偶然死んでしまうという可能性はないのかな。


もし、この問題が現実のお話だったら、その可能性を排除できませんが、

あくまで架空のこの手の問題で、

他の別な要因で偶然死ぬ
特異体質で毒が効かない奴隷がいた。
毒を飲まされるのを察知した奴隷が、飲んだふりをして実は飲んでなかった

などなどの要因を考える必要はありません。っていうかそんなことを考えてたら問題解けませんw

ではでは~

作成者:  通りすがり [ 2014/08/04 13:13 ]
記事の件名:  Re: 毒入りワインを発見する問題

今更ですみなせん。ちょっと気になったので質問させていただきます。
毒で死ぬ時間が20時間だと固定した場合、
この方法だと24時間以内に最大10本に絞る方法ではありませんか?

作成者:  通りすがり [ 2016/06/26 16:38 ]
記事の件名:  Re: 毒入りワインを発見する問題

 毒入りが2本含まれる場合について、
1本を含む場合のような2進法の考え方や対数、組合せの考えも無意味
ではないかと思います。
答は999人、という解に至ったので、以下に述べます。
(長くなってしまいます)


 まず、毒入りが1本の場合とは決定的に違う点は、
出力のパターンを分化できても、それを創る要素が2元的なので
その2本の行方まで追いきれない、ということです。
 例えば、(※今後、奴隷とその飲むワインの組を表で示しますが、
      横向きにワイン、縦向きに奴隷が増える表です。
      "0"は飲まない、"1"を飲むとします。)
2人の奴隷に4本のワインを毒味させようとすると、、

      ワイン
      ① ② ③ ④ 
 奴隷 A 1 1 0 0
    B 1 0 1 0

という飲ませ方を考えます。
これで組合せの場合分けはできているように思えます。ところが、
①のワインに毒が入っていた場合、A、Bともにお亡くなりに
なってしまうので、このとき、①に毒が入っていたことのみが確認され
もう1本の毒ワインについては行方不明です。すなわち、この方法は
確実に毒入りを「特定」する方法ではないということです。

 このようなことを念頭に置いて話を進めます。
奴隷が2人のときには、特定できるワインの最大本数は3本です。

   ① ② ③
 A 1 0 0
 B 0 1 0

 一般化として、奴隷がn人、ワインがW本となったときの判別方法を考えます。
 もしも、ある1本のワイン(例えば①)をすべての奴隷が毒味したとすると、
他のワインについてどの奴隷がどう飲んだかに関わらず
最初の例のように、そのワインに毒が入っていた(という不運な)ときに
「全滅」という結果だけが得られ、①以外のワインについては確かめられません。
 では、1人(例としてnさん)を除いて他全員が①を飲むとどうでしょうか。
この場合も、①が毒だったときには1人以外は等しく死んでしまうので、
その奴隷たちが他のどのワインを飲んだとしても、毒の特定には
効力がなくなってしまいます。

   ① ② ③ ④ ⑤・・・W
 A 1   無意味
 B 1   無意味
 C 1   無意味
 D 1   無意味
 ・
 ・
 ・
 n 0 1人で判別不可

 そうなると、残されたnさん1人に毒1本の捜索が委ねられる
わけですが、それはせいぜい2本から探る程度であり、特定は無理です。

 規模を縮小してみますが、ある1本のワインを2人以上が
飲んだ場合についてはすべて、同様になります。すると、

   ① ② ③ ④         ① ② ③ ④
 A 1  無意味   同価値  A 1 0 0 0
 B 1  無意味    =   B 0 1 0 0
 C 0 1 0 0       C 0 0 1 0
 D 0 0 1 0

というように、ある1つのワインを複数人で毒味しても、それは特定のための
データの増加にはなりません。それは、どのワインについてもすべて言えます。

 あとは個人の理解に任せられるかもせれませんが、

「奴隷が1人増えたとき、特定できるワインの最大数を増やすためには
他のどの奴隷も飲んでいない新しいワインを飲む。また、そのワインを
他の奴隷が飲むこともない。」
という条件が発見されたことになります。
 さらに、1人の奴隷が2本のワインを飲んでも、その奴隷が死んだときに
どちらのワインが原因であるのかはわからないので、総じて
「1人の奴隷が飲むワインは一本」というわけです。

 これが解に直結しますね。
1本分は「無情報という情報」によって飲まなくていいとしても、
計1,000本のワインを選別するためには、999人の奴隷が必要です。


 数式で表したり、帰納法的に証明することもできるとは思いますが
省きました。おそらく正しいはずですが、適当に検証してください。

長文、すみません。

ページ 22 All times are UTC + 9 hours
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/