日本バックギャモン協会

バックギャモンに関する疑問や、本サイトの感想等がありましたら、お気軽にお書きください。
現在時刻 - 2024/03/29 02:02

All times are UTC+09:00




返信する
ユーザー名:
件名:
メッセージ本文:
メッセージを入力してください。60000 字まで入力できます。 

オプション:
BBCode: OFF
スマイリー: OFF
URL を自動的にパースしない
クイズ
協会名の正式名称を入力してください。ヒント: ページ上部に答えがあります。(スパムボット認証):
答えを正確に入力してください。答えられるかどうかでスパムボットか否かを判定します。
   

トピックのレビュー - 毒入りワインを発見する問題
作成者 メッセージ
  記事の件名:  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人の奴隷が必要です。


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

長文、すみません。
投稿記事 Posted: 2016/06/26 16:38
  記事の件名:  Re: 毒入りワインを発見する問題  引用付きで返信する
今更ですみなせん。ちょっと気になったので質問させていただきます。
毒で死ぬ時間が20時間だと固定した場合、
この方法だと24時間以内に最大10本に絞る方法ではありませんか?
投稿記事 Posted: 2014/08/04 13:13
  記事の件名:  Re: 毒入りワインを発見する問題  引用付きで返信する
引用:
毒の入っていないワインを飲んだ奴隷が、何か他の要因で10~20時間以内に偶然死んでしまうという可能性はないのかな。
もし、この問題が現実のお話だったら、その可能性を排除できませんが、

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

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

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

ではでは~
投稿記事 Posted: 2014/04/18 13:06
  記事の件名:  Re: 毒入りワインを発見する問題  引用付きで返信する
毒の入っていないワインを飲んだ奴隷が、何か他の要因で10~20時間以内に偶然死んでしまうという可能性はないのかな。
投稿記事 Posted: 2014/04/09 02:18
  記事の件名:  Re: 毒入りワインを発見する問題  引用付きで返信する
引用:
ところでこの問題、毒入りワインを飲むと10~20時間の間に死ぬ、とありますが「誰が飲んでもぴったり同じ時間で死ぬ」という風に解釈したら2人で十分だということに気づきました。
ごめんなさい、毒入りワインが1本の場合の話です。

長々と失礼しました。
投稿記事 Posted: 2014/04/08 22:34
  記事の件名:  Re: 毒入りワインを発見する問題  引用付きで返信する
引用:
また、2^19がミニマムだという証明はできないと言ってました
最低でも19人必要というのは間違いないと思うのですが、19人で十分だというためには戦略を示す必要があると思います。
ちなみになぜ19人かと言うと、「出力の組み合わせ」が「入力の組み合わせ」を上回るための最低限の人数だからです(下式参照)。出力の組み合わせ数のほうが少ないと、同じ出力に2つ以上の入力が対応するケースが必ず存在し、出力結果(奴隷の生死)から入力(ワインの在り処)判断できないからです。

18人の生死の組み合わせ < 毒入りワイン2本の組み合わせ < 19人の生死の組み合わせ
 → 2^18 < 1000×999÷2 < 2^19
引用:
ブログで書きますと言ってましたが
いつの間にかブログに書くことになっている、、、、、
結構な時間、考えたのですが19人で出来る戦略は全く思い浮かびませんでした。誰か思いついた人がいれば教えて欲しいです。

ところでこの問題、毒入りワインを飲むと10~20時間の間に死ぬ、とありますが「誰が飲んでもぴったり同じ時間で死ぬ」という風に解釈したら2人で十分だということに気づきました。
投稿記事 Posted: 2014/04/08 22:31
  記事の件名:  Re: 毒入りワインを発見する問題  引用付きで返信する
世界発信されるとわかっていれば、もっときれいな字で書けばよかったです。。

2本両方飲むと死ぬケース、1本でも飲むと死ぬケースで必要な奴隷の人数は同じだと思います。生死からわかる情報量がちょうど反対になっているからです。

<2本両方飲むと死ぬケース>
 死んだ : 飲んだワインの中に毒入りワインが2本存在する
 生きてる: その他

<1本でも飲むと死ぬケース>
 生きてる: 飲まなかったワインの中に毒入りワインが2本存在する
 死んだ : その他

死んだ/生きてる、 飲んだワイン/飲まなかったワイン、 の部分がちょうどひっくり返っています。片方のケースでX人で出来る戦略があるなら、飲むワインを逆にして生死の結果を逆に考えれば、もう片方のケースでも同じ人数で出来るはずです。
※この説明は奴隷にワインを一斉に飲ませることを前提としていて、生死の結果に応じて飲ませ方を変えたり、飲むタイミングを変えるような戦略を考慮していません。自明にも思えるのですが、数学的に証明しようとすると案外難しいと思います。
投稿記事 Posted: 2014/04/08 21:51
  記事の件名:  Re: 毒入りワインを発見する問題  引用付きで返信する
引用:
2本の毒ワインを両方飲んだ時だけ死ぬなら19人だと思うのですが、どちらを飲んでもしぬっなると、もっと必要なきがします。
とりあえず999人だと確実なんだけど、それより減らせるかな。
久保田奏さんが赤坂例会で毒ワイン問題についてレクチャーしてくれました。
2本の毒ワインを両方飲んだ時に死ぬ、という条件と2本の毒ワインの片方だけ飲んでも死ぬ、という条件で
答えは全く同じになるそうです。(添付写真参照)

また、2^19がミニマムだという証明はできないと言ってました。もっとも、こちらは本人も
難しくて考え中で、確信はなさそうでした。ブログで書きますと言ってましたが。右上の辺りです。
添付ファイル:
KIMG0474.jpg
KIMG0474.jpg [ 241.35 KiB | 閲覧された回数 19267 回 ]
ということで、正解を知っていたら発表をお願いします。
投稿記事 Posted: 2014/04/07 01:31
  記事の件名:  Re: 毒入りワインを発見する問題  引用付きで返信する
ワインに1から1000まで番号を振る。

それを2進数に変換する。1000なので、2の10乗、1024で足りるから、10桁あれば良い。
コップを10個用意する。 A B C D E F G H I J と名前を付ける。

         A B C D E F G H I J
1番のワイン 0 0 0 0 0 0 0 0 0 1
2番のワイン 0 0 0 0 0 0 0 0 1 0
3番のワイン 0 0 0 0 0 0 0 0 1 1

1000番の
ワイン     1 1 1 1 1 0 1 0 0 0

1番目のワインは、 J に一滴入れる。
3番目のワインは、I と J に一滴ずつ入れる。
1000番目のワインは、A,B,C,D,E,G に一滴ずつ入れる。

一人目の奴隷には A のコップを
二人目の奴隷には B のコップを
以下同様に
十人目の奴隷には J のコップを
飲ませる。

20時間待つ。ここまでの説明で分かる人はもう、答えは分かりますよね?
分からない人にどう説明すればよいか分かりません。w
二進数とは何かから説明するのはしんどいです。w

とりあえず、最初の答えです。
投稿記事 Posted: 2014/03/25 12:19
  記事の件名:  Re: 毒入りワインを発見する問題  引用付きで返信する
回答はいつ発表なんですか?
投稿記事 Posted: 2014/03/25 09:30
  記事の件名:  Re: 毒入りワインを発見する問題  引用付きで返信する
どちらを飲んでも死ぬという条件で必要な奴隷の数が19人で間違いないと思います。
むしろ、両方飲んだ場合だけ死ぬと言う方が、めちゃくちゃたくさんの場合の数が必要になります。
投稿記事 Posted: 2014/03/23 14:07
  記事の件名:  Re: 毒入りワインを発見する問題  引用付きで返信する
2本の毒ワインを両方飲んだ時だけ死ぬなら19人だと思うのですが、どちらを飲んでもしぬっなると、もっと必要なきがします。
とりあえず999人だと確実なんだけど、それより減らせるかな。
投稿記事 Posted: 2014/03/22 10:49
  記事の件名:  Re: 毒入りワインを発見する問題  引用付きで返信する
毒ワインが2本なら、19人になるはずですね。
飲ませ方までちゃんと説明は出来ないけど、19人であっていると言うことは99%間違いないです。
投稿記事 Posted: 2014/03/22 07:32
  記事の件名:  Re: 毒入りワインを発見する問題  引用付きで返信する
某氏から、問題改変のお知らせが来た。

他の条件は一緒で、毒ワインが2本ある。
奴隷は最低何人必要でしょうか?

なかなか面白い。w
投稿記事 Posted: 2014/03/22 05:04
  記事の件名:  Re: 毒入りワインを発見する問題  引用付きで返信する
僕も出来ましたー

毒入りを判断するためには人が死ぬのを確認するしか無いんですけど、
じゃあどう死んでもらえば(言い方が物騒ですね)早く見つけることができるかっていう発想に移るのが難しいんですかね ある程度の基礎知識も無いといけませんが
投稿記事 Posted: 2014/03/21 19:54

All times are UTC+09:00


ページ移動:  
cron
Powered by phpBB® Forum Software © phpBB Limited
Japanese translation principally by ocean