ワイン問題詳しく

http://d.hatena.ne.jp/nokuno/20110802/1312236781で紹介されている@http://twitter.com/neubig さんの問題について、id:nokuno さんの解説に加え、具体的な答えを書いてみる。


問題を改めて引用。

元記事にもあるように、1日しかない場合は

紙切れ0につけるワイン＝{4,5,6,7}
紙切れ1につけるワイン＝{2,3,6,7}
紙切れ2につけるワイン＝{1,3,5,7}

というやり方で、3つとも溶けたらワイン7、2つ溶けたら溶けた紙切れによってワイン3, 5, 6、1つ溶けたら溶けた紙切れによってワイン1, 2, 4、一枚も溶けなかったらワイン0というのが答え。

どれにもつけないワインを明示的に書くと、次のようになる。

紙切れ0につけるワイン＝{4,5,6,7}
紙切れ1につけるワイン＝{2,3,6,7}
紙切れ2につけるワイン＝{1,3,5,7}
どれにもつけないワイン＝{0}

で、2日ある場合。

仮に、1日しかない場合と同じような紙の使い方をするとする。この場合、例えば 紙切れ 1 だけが溶けたとすると、2番のワインが毒だとわかって、紙切れ 0 と 2 の 2枚が残ることになる。


2枚の紙が残るということは、4本のワインの判別ができる。ということは、「2番」の 1本に絞らなくても、4本にまで絞っていればよかったということになる。


これを踏まえて、2番のワインを 2, 2', 2'', 2''' と置き換えると、次のようになる。

紙切れ0につけるワイン＝{4,5,6,7}
紙切れ1につけるワイン＝{2,2',2'',2''',3,6,7}
紙切れ2につけるワイン＝{1,3,5,7}
どれにもつけないワイン＝{0}

もし紙切れ 1 だけが溶けていたら、毒入りワインは 2, 2', 2'', 2''' のどれかで、紙切れ 0 と 2 を使って判別ができる。

同じように、1番と 4番のワインもそれぞれ 4本で入れ替える。

紙切れ0につけるワイン＝{4,4',4'',4''',5,6,7}
紙切れ1につけるワイン＝{2,2',2'',2''',3,6,7}
紙切れ2につけるワイン＝{1,1',1'',1''',3,5,7}
どれにもつけないワイン＝{0}

他の場合として、紙切れ 0 と 2 が溶けるというような場合を考える。この時、毒入りは 5番。しかし、紙切れ 1 が残っているので、2本に対して判別ができる。

これを踏まえて、5番のワインを 5, 5' と置き換えると、次のようになる。

紙切れ0につけるワイン＝{4,4',4'',4''',5,5',6,7}
紙切れ1につけるワイン＝{2,2',2'',2''',3,6,7}
紙切れ2につけるワイン＝{1,1',1'',1''',3,5,7}
どれにもつけないワイン＝{0}

紙切れ 0 と 2 が溶けていたら、毒入りワインは 5 か 5' で、紙切れ 1 を使って判別ができる。

同様に 3番と 6番もそれぞれ 2本に増やすと、次のようになる。

紙切れ0につけるワイン＝{4,4',4'',4''',5,5',6,6',7}
紙切れ1につけるワイン＝{2,2',2'',2''',3,3',6,6',7}
紙切れ2につけるワイン＝{1,1',1'',1''',3,3',5,5',7}
どれにもつけないワイン＝{0}

紙が全部溶ける場合は、それ以上判別ができない。だから、紙が全部溶けたときに毒入りとわかる 7番はそのまま。


紙が一枚も溶けない場合は、毒入りワインは 0番だとわかる。しかし、この場合は 3枚の紙を使って 8通りの判別ができる。だから、0番のワインは 8本に増やせる。

紙切れ0につけるワイン＝{4,4',4'',4''',5,5',6,6',7}
紙切れ1につけるワイン＝{2,2',2'',2''',3,3',6,6',7}
紙切れ2につけるワイン＝{1,1',1'',1''',3,3',5,5',7}
どれにもつけないワイン＝{0,0',0'',0''',0'''',0''''',0'''''',0'''''''}

どの紙も溶けなければ、毒入りワインは 0, 0', ... の 8本のうちのどれかで、3枚の紙切れを使って判別できる。


ちょっと馬鹿らしいほどダッシュが多くなってしまった。番号を振り直すと、次のようになる。

紙切れ0につけるワイン＝{16,17,18,19,22,23,24,25,26}
紙切れ1につけるワイン＝{12,13,14,15,20,21,24,25,26}
紙切れ2につけるワイン＝{8,9,10,11,20,21,22,23,26}
どれにもつけないワイン＝{0,1,2,3,4,5,6,7}

こうすることで、溶けた（溶けない）紙切れによって毒入りワインが 1/2/4/8 本に絞られ、その後残った紙を使って再度判別を行うことで 1本に答えを絞ることができる。


ところで、元ツイートにも URL がある通り、これには英語の元ネタがあるのだが、この問題ではマイルドに改変してある。元ネタを直訳すると次のようになる。

「あなたは X-treme Water の新しいプロトタイプを 27容器分持っているのだが、その中のちょうどひとつだけが珍しい Q型肝炎ウィルスによって汚染されている。このウィルスを飲むと一日以内に死んでしまう。幸い、前回あなたのバイラル広告担当だった 3人のマーケティング責任者がいて、彼らは使い捨て可能である。2日以内に汚染された容器を見つけよ（m人のマーケティング責任者と d日で、何個の容器を扱えるか？）」