1000本の毒入りワインの論理パズル
なんかスランプというかなんというかブログが書けない病気になっちゃったので気晴らしにまったくFGOと関係ない話題で1つ記事を書いてみようと思います。テーマは毒入りワインの論理パズルです。なんやそれ？ って思うかも知れませんが今から説明します。
1000本のワインがあってその中の1本にだけ毒が入っている。その毒は飲んだら10～20時間の間のある時間で死ぬ。貴方には毒味をさせる奴隷が何人かいる。さて、今から24時間以内にどのワインに毒が入っているか特定したい。最低何人の奴隷が必要であろうか？ ただし1人の奴隷には何本のワインを飲ませても良い。
という問題です。どこにでもありそうな論理パズルといやつですね。さて皆さん解けるでしょうか？ 簡単そうに見えてこういう「最小値はいくら？」というような形式というやつはなかなか厄介ですよね。どうやって解いてももっと下がないことはなかなか論理的に納得できません。これが最小だろ！ って思っても実はもっと下がありうる、そういう恐怖があるわけですよね。ですからどんなに小さくてもまだ慢心できない。人工知能に解かせるとしたらある意味一番やっかいなタイプの問題ですね。
さて、ここでうだうだ書いていても仕方ないのでこの問題について解説していきましょう。
以下順に回答を書いていきますので、自力で解きたい人はよく考えてから見ていってください。
さて、まず結論から言うとよく知れた答えは10人です。
「えぇ～？ ほんとにござるかぁ？」
とか言いたくなるかも知れませんがまあ10人でいけちゃうんですよね。さてそれでは考えの流れを順に見ていくとしましょう。
以下奴隷に(1)～(500)、ワインに[1]～[1000]までの番号をつけます。
1. 1000人
1000人に1本づつ同時に飲ませれば最悪でも20時間かかり、どのワインかわかる。よって答えは1000人や！！
→流石にもっとがんばりましょう。
2. 999人
よく考えたら999本飲んで全員死ななければ残りが毒入りってわかるし死んだ人いたらそのワインだから999人でよくね？ (ﾟ∀ﾟ)ｷﾀｺﾚ!!
→気持ちはわかる。
3. 500人
よくよく考えたら500人で良くね？ 1人1本飲ませたら1000人なんだから1人2本飲ませれば半分じゃん！ 例えば、(1)に[1]と[501]を(2)に[2]と[502]を……(500)に[500]と[1000]を飲ませればOKじゃん！
でもそれだと(1)が死んでも[1]か[501]までしかわからない……。せや！ (1)に[1]と[501]と[500]を飲ませて、(2)には[2]と[502]と[1]を飲ませて……(500)には[500]と[1000]と[499]を飲ませればいけるやん！ そうすればまず(1)が死んだ場合[1]か[501]まで絞れる。ここもし(2)が死んでたら[1]、死んでなかったら[501]だ！！ (ﾟ∀ﾟ)ｷﾀｺﾚ!!
→いい発想です。それをもっと掘り下げるのです。
4. 250人
さらに半分行けない？ 1人4本飲ませるんだ。まず(1)に[1][251][501][751]とを飲ませる。(2)には[2][252][502][752]を飲ませる……(250)には[250][500][750][1000]を飲ませる。これだと(1)が死んでも4択にしかならない。そこで、(2)に[1]を飲んでもらい、(3)に(251)を飲んでもらい、(4)に(501)を飲んでもらう。代わりに(1)は[250][249][498]を追加で飲む。それをみんなで回せば特定できますね。ちょっとわかりにくい……？
う～ん。わかる。ワイもわかりにくいわ。つまり、(n)は[n][250+n][500+n][750+n]と[n-1]*1[250+n-2][500+n-3]を飲むわけです。自分の持ち分プラス1つ前の人の1本目、2つ前の人の2本め、3つ前の人の3本目を飲むのです。これで誰が死んだかで特定ができますね？ (1)が死んだ場合[1][251][501][751]の4択という発想でしたが、ここで、[1]だった場合は(1)(2)だけが死ぬし、(1)と(2)とが死んだ場合は[1]だとわかります。[251]だった場合は、(1)と(3)が死ぬし、(1)と(3)が死ねば、[251]だと分かります。[501]だった場合は、(1)と(4)が死ぬし、(1)と(4)が死ねば[501]だと分かります。そして[751]だった場合(1)だけが死ぬし、(1)が死んだとすると[751]だとわかります。という流れで度のワインか特定できちゃうわけです。だんだん厳しくなってきた……。
5. 125人
同じ原理で更に半分にできます。(1)が死んだ時点で8パターン、7つ隣の人にまで協力を仰ぐことになります。
6. 63人
125は半分で割れないですが小数点切り上げの63人ならいけます。これは空のワインを8本、[1001]～[1008]を追加するとすんなり行くのですが、これについても後で説明いたしましょう。15個隣の人にまで協力を仰ぐことになります。
7. 33人
まだいけます。今までと同じです。31個隣の人にまで協力を仰ぐことになります。
8. 17人？
さて、このままどんどんと半分にしていきたいわけですが、どうしてもそれは続きません。それは次の125が奇数だからではなくて、1回割ると500人で1隣の人、2回割ると250人で3つ隣の人、3回割ると125人で7つ隣の人、4回割ると63人で15つ隣の人、5回割ると32人で31つ隣の人が必要になりますが……32人で31つとなりということはそこで頭打ちということになります。つまり答えは33人！ もし仮にここまで思いついた人いたらすごいです。
9. 10人
さて、今まで上手くパターンを分配してやれば半分にできる、という話をしてきました。これはこの問題の本質が、いかにして1000のパターンを各人の生死で網羅するか、という事になってきたことがわかるでしょうか？ ちょっとわかりにくいかもですね。少々天下りですが10人のパターンはこの発想からたどり着きます。
各奴隷に何かしらワインを飲ませるパターンを考えましょう。この時、奴隷は生きてるか、死ぬかのどちらかの2パターンがありますね？ つまり2人の奴隷がいた場合、(1)が{生,死}、(2)の{生,死}で2×2の4パターンがありますね？ (生,生)(生,死)(死,生)(死,死)です。つまり10人の人がいた場合は2×2×2×…×2=1024パターンあるわけです。たった10人の生死だけで1024ものパターンが作れるというのは改めて考えると驚きですね。
そして、仮にもしこの1024のパターン全てに毒入りワインがどれであるかを対応させるとことができれば、死んだ人のパターンから毒入りがどれか特定できるということになります。はたしてそんなことできるのか？ 結論から言うとできるわけです。しかし、その説明は難しいです。なぜか？ だって、1人あたり512本飲むのでとてもじゃないですが書ききれません。具体例を示すのが1番のはずなのにそれが出来ないのでどうやったって難しい説明になってしまいます。それでも言い方は続けましょう。
1023本のワインに番号次のようにラベルを張ります。[0000000001]～[1111111111]。ここで、各奴隷には以下のような規則でワインを飲ませます。
(1)は1桁目が1のワインを飲め。つまり[0000000001],[0000000011],[0000000101],……,[1111111111]を飲め。
(2)は2桁目が1のワインを飲め。つまり[0000000010],[0000000011],[0000000111],……,[1111111111]を飲め。
…
(10)は10桁目が1のワインを飲め。つまり[1000000000],[1000000011],[1000000101],……,[1111111111]を飲め。
つまりみんな全体の半分のワインを飲むことになります。問題文に何本でも飲んでいいと書きましたが512本もワインを飲むのはイカれてますね笑
さて、実は上の飲ませ方で死んだ人によってどのワインが毒入りか分かります。それは、例えば[1001010101]が毒入りだったとしましょう。この時[1001010101]を飲んだのは(1)(3)(5)(7)(10)の5人ですね？ つまり、この5人だけが死にます。逆にこの5人だけが死んだ場合は毒入りは[1001010101]以外ありえません。なぜなら別のワインに毒が入っていたとするとある部分が[1001010101]と異なります。たとえば[1010010101]が毒入りだっとすると死ぬのは(1)(3)(5)(8)(10)でなくてはなりません。つまり他のワインということはありえません。以上から上のようなラベル付けから毒入りが判別できるのです。
ちょっと難し目の説明でしたが理解できましたか？ たった10人でできることにシンプルな驚きがありますね。というわけで毒入りワイン問題はこれにて終了です。
……。
……。
なあんてな！
10. EXTRA STAGE
誰が10人が最小だって言った？ 甘い！！ 甘すぎる！ そんなんじゃ過酷あふれる魔術師の世界を生き残ることはできない。最初に書いたとおり最小値問題というのはいくら下げても慢心できません。いったいどうして10人で慢心できるというのでしょうか？ さて、エクストラステージを初めましょう。
1000本のワインがあってその中の1本にだけ毒が入っている。その毒は飲んだら10～20時間の間のある時間で死ぬ。貴方には毒味をさせる奴隷が何人かいる。さて、今から24時間以内にどのワインに毒が入っているか特定したい。最低何人の奴隷が必要であろうか？ ただし1人の奴隷には何本のワインを飲ませても良い。
この問題を最初に見て思うのは多分、0時間と4時間の時間差飲ませではないでしょうか？ 自分はそうでした。先程の回答はどういうわけか24時間という制限をガン無視してしまっています。何か腑に落ちません。しかし普通に時間差飲ませをすると例えば14時間後に死んだ時。14時間のワインで死んだのか、4時間後に飲ませた10時間ワインで死んだのか判別が付きません。時間がわからないという条件が意外と邪魔くさいのです。
つまり時間がわかれば良いのです。
発想は2つ。
- ワインが何時間で死ぬか分かっていたとすると時間差の飲ませでいけそう。
- 1人が死ねば時間が特定できる。
つまり次のようにやります。必要な奴隷は2人です。
- (1)の奴隷
- 始まった瞬間1000本のワインをすべて飲ませる。
- (2)の奴隷
- 始まった瞬間から10秒ごとに1本、[1]から順にワインを1000本飲ませる。
まず、ある特定の時間で(1)の奴隷は死にます。この尊い犠牲により時間が特定できます。さて、ここで、(1)が死んだと同時に(2)も死ねば、[1]が毒入りワインと分かりますね？ 同タイミングで飲んだのは[1]だけですから。次に(1)が死んだ10秒後に(2)が死ねば[2]が毒入りワインだと分かります。さらに(1)が死んだ20秒後に(2)が死ねば[3]が毒入りワインだと分かります。……(1)が死んだ10000秒後に(2)が死ねば[1000]が毒入りワインだと分かります。これにより毒入りワインを特定することができるのです。ストップウォッチを滅茶苦茶集中して押しましょう。少しの誤差が命取りです。まだ、奴隷にはしっかりワインを飲ませましょう。少しの誤差が命取りです。ワインの効き目の個人差なんて知りません。そんなものを考慮して論理パズルを解くのはあまっちょろいです。
想像するとかなり気が狂った情景がそこにはありますが気にしてはいけません。これくらいの狂気で挑まないと勝負の世界ではやっていけません(何と戦っているんだ……)。
ちなみに実は1000本ではなく999本でOKです。(1)が死ななければそれで最後の1本とわかりますからね。必ず死ぬと知ったら抵抗されかねないので少し(0.1%)だけ人道的にしましょう。というか10人の方法は期待値的には5人は死にますが、こちらは基本的には2人しか死にません。切嗣も選ぶならこちらの方法でしょう。(ケイネスならいかにも前者を選びそう)
以上！ 最後のどんでん返しみたいなのが書きたくてこの記事を書きました。この問題についてこの回答を提示している人がいなかったので、というのもあります。結構書いてて楽しかったです。
もし2人より少ない回答があったら2人で慢心している僕にぶつけてきてください。当たり前ですが、タイムマシンとか超能力とか特異体質とかそういうのはなしで、論理パズルの範疇でですよ！ あと、自分でも飲めば奴隷は1人で済むとかもダメですよ！
そんなわけでもし更に少ない方法が見つけられたら、完敗です。You winner! Chicken Dinner!
皆さんの挑戦、待ってますよ！！
*1:ただし0の場合は250とする
