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

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

作成者:  kinchan [ 2014/03/19 17:33 ]
記事の件名:  毒入りワインを発見する問題

■ 毒入りワインを発見する問題
 
1000本中1本のみ毒の入ったワインがあります。
毒入りのワインを1滴でも飲むと10~20時間で死に至ります。
奴隷を使って毒入りのワインを24時間以内に特定するには、奴隷は最低何人必要か答えなさい

作成者:  key [ 2014/03/20 05:11 ]
記事の件名:  Re: 毒入りワインを発見する問題

10人。飲ませ方も全部説明済み。
およそ15分で出来ました。この手の問題は得意です!

作成者:  kinchan [ 2014/03/20 07:30 ]
記事の件名:  Re: 毒入りワインを発見する問題

key さんが書きました:
10人。飲ませ方も全部説明済み。
およそ15分で出来ました。この手の問題は得意です!


はい、正解です。ぱちぱちぱち。
「飲ませ方も全部説明済み」ってところがちょっと意味不明だけどw

http://blog.livedoor.jp/kinisoku/archives/4023190.html

からの引用です。

「これが自力で解けたらiQ136以上らしい」

って書いてあったけど、これはちょっと怪しいかも w

ちなみに、10~20時間で死に至る 部分を、10時間で死に至る に問題を改変すると、9名と答える方、いらっしゃりそうな気がする。
(はい、それは私です。ごめんなさい。w)

あることに気づくまでが勝負ですよね。
多分、コンピュータ関係の人の方が有利でしょうね。

ではでは~

作成者:  key [ 2014/03/20 10:39 ]
記事の件名:  Re: 毒入りワインを発見する問題

飲ませ方も説明済みというのは、10人にどういう風に飲ませればよいかを正しく説明出来ると言う意味です。大学入試で満点もらえる回答と言う意味。

ちなみに、10人と言うことは、問題を見て5秒で分かり、1分で確信持てました。
後は検証です。

IQは関係ないと思うなあ。単なる慣れじゃないかと。

作成者:  flappy [ 2014/03/21 19:54 ]
記事の件名:  Re: 毒入りワインを発見する問題

僕も出来ましたー

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

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

某氏から、問題改変のお知らせが来た。

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

なかなか面白い。w

作成者:  key [ 2014/03/22 07:32 ]
記事の件名:  Re: 毒入りワインを発見する問題

毒ワインが2本なら、19人になるはずですね。
飲ませ方までちゃんと説明は出来ないけど、19人であっていると言うことは99%間違いないです。

作成者:  某氏 [ 2014/03/22 10:49 ]
記事の件名:  Re: 毒入りワインを発見する問題

2本の毒ワインを両方飲んだ時だけ死ぬなら19人だと思うのですが、どちらを飲んでもしぬっなると、もっと必要なきがします。
とりあえず999人だと確実なんだけど、それより減らせるかな。

作成者:  key [ 2014/03/23 14:07 ]
記事の件名:  Re: 毒入りワインを発見する問題

どちらを飲んでも死ぬという条件で必要な奴隷の数が19人で間違いないと思います。
むしろ、両方飲んだ場合だけ死ぬと言う方が、めちゃくちゃたくさんの場合の数が必要になります。

作成者:  望月 正行 [ 2014/03/25 09:30 ]
記事の件名:  Re: 毒入りワインを発見する問題

回答はいつ発表なんですか?

作成者:  kinchan [ 2014/03/25 12:19 ]
記事の件名:  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

とりあえず、最初の答えです。

作成者:  望月 正行 [ 2014/04/07 01:31 ]
記事の件名:  Re: 毒入りワインを発見する問題

某氏 さんが書きました:
2本の毒ワインを両方飲んだ時だけ死ぬなら19人だと思うのですが、どちらを飲んでもしぬっなると、もっと必要なきがします。
とりあえず999人だと確実なんだけど、それより減らせるかな。


久保田奏さんが赤坂例会で毒ワイン問題についてレクチャーしてくれました。
2本の毒ワインを両方飲んだ時に死ぬ、という条件と2本の毒ワインの片方だけ飲んでも死ぬ、という条件で
答えは全く同じになるそうです。(添付写真参照)

また、2^19がミニマムだという証明はできないと言ってました。もっとも、こちらは本人も
難しくて考え中で、確信はなさそうでした。ブログで書きますと言ってましたが。右上の辺りです。

添付ファイル:
KIMG0474.jpg
KIMG0474.jpg [ 241.35 KiB | 表示数: 15420 回 ]


ということで、正解を知っていたら発表をお願いします。

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

世界発信されるとわかっていれば、もっときれいな字で書けばよかったです。。

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

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

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

死んだ/生きてる、 飲んだワイン/飲まなかったワイン、 の部分がちょうどひっくり返っています。片方のケースでX人で出来る戦略があるなら、飲むワインを逆にして生死の結果を逆に考えれば、もう片方のケースでも同じ人数で出来るはずです。
※この説明は奴隷にワインを一斉に飲ませることを前提としていて、生死の結果に応じて飲ませ方を変えたり、飲むタイミングを変えるような戦略を考慮していません。自明にも思えるのですが、数学的に証明しようとすると案外難しいと思います。

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

望月 正行 さんが書きました:
また、2^19がミニマムだという証明はできないと言ってました

最低でも19人必要というのは間違いないと思うのですが、19人で十分だというためには戦略を示す必要があると思います。
ちなみになぜ19人かと言うと、「出力の組み合わせ」が「入力の組み合わせ」を上回るための最低限の人数だからです(下式参照)。出力の組み合わせ数のほうが少ないと、同じ出力に2つ以上の入力が対応するケースが必ず存在し、出力結果(奴隷の生死)から入力(ワインの在り処)判断できないからです。

18人の生死の組み合わせ < 毒入りワイン2本の組み合わせ < 19人の生死の組み合わせ
 → 2^18 < 1000×999÷2 < 2^19

望月 正行 さんが書きました:
ブログで書きますと言ってましたが

いつの間にかブログに書くことになっている、、、、、
結構な時間、考えたのですが19人で出来る戦略は全く思い浮かびませんでした。誰か思いついた人がいれば教えて欲しいです。

ところでこの問題、毒入りワインを飲むと10~20時間の間に死ぬ、とありますが「誰が飲んでもぴったり同じ時間で死ぬ」という風に解釈したら2人で十分だということに気づきました。

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

引用:
ところでこの問題、毒入りワインを飲むと10~20時間の間に死ぬ、とありますが「誰が飲んでもぴったり同じ時間で死ぬ」という風に解釈したら2人で十分だということに気づきました。


ごめんなさい、毒入りワインが1本の場合の話です。

長々と失礼しました。

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