LogicNovel|AboutContact

殿様と毒入りワイン

問題

殿様は毎年部下からワインを受け取ることになっています。今年は1,000本のワインが集まりました。

しかし、どうやら1本だけ毒入りワインが混じっているようです。

殿様は部下にワインを毒身させ、24時間以内に毒入りワインを特定したいと思っています。

毒入りのワインを特定するには最低何人の部下が必要でしょうか?

条件は以下の通りです。

  • 毒入りワインを1滴でも飲むと、10~20時間(正確な時間は分からないしワインによって異なる)で死にます。
  • 毒入りのワインは見た目や重さも他のワインと全く一緒です。

ヒント

当然ですが、答えは1000人ではありません。

1000本のワインではなく、4本のワインだったらどうなるかを考えると答えに近づきます。

正解

答えは10人です。それでは、順番に解き方を見ていきましょう。

ヒントに書いたようにまずは4本のワインで考えてみます。

1, 2, 3, 4のワインの一つに毒が入っていると考えます。

この場合部下は2人で十分です。1, 2のワインを部下Aが飲み、1, 3のワインを部下Bが飲みます。

ABが死んだら毒入りワインは1です。Aだけが死んだら毒入りワインは2です。Bだけが死んだら3、ABどちらも死ななかったら4が毒入りワインです。

 

つまり、n人の部下で、2^nのワインを判定できることになります。

部下が10人いると、2^10 = 1024個のワインを判定できます。