質問: 24時間以内に死ぬ毒が入ったワインが1000本あります。この中から毒入りのワインを見つけ出すには最低何人の奴隷を使う必要があるでしょうか? というクイズがあります。 答えは10人だそうです
回答: 設問が元の問題と違うのでもう一度言い直させてもらいます。 「24時間以内に死ぬ毒が入ったワインがあるが、確実な時間はわからない。しかし一日のうちに、この中から毒入りのワインを見つけ出すには最低何人の奴隷を使う必要があるでしょうか?」 が元の問題でした。ここで時間の条件を足した理由は、奴隷が「一度」に飲む必要があるからです。この点こそがこの問題の一番難しいところなのです。 皆さんの回答を見ていると、すでに死人が出ている(つまり結果を一部知っている)状態で更に2度3度と飲む行為を行っているので、正しい解説とはいえません。 (1日のうちに、という時間の条件がなければ、1000日かけて1人が1本ずつ飲んでいくというのも可能になるからです。) 1000=2^xという考えは間違っていませんが、本質的な理解をするために逆から攻めて行こうと思います。 まず1人だと一度にワインをどれくらい測ることが出来るでしょうか。 答えは2本です。1本は飲む、もう片方は飲まない。こうすることでこの人が死ぬか死なないかで毒ワインがどちらかがわかります。 では2人ではどうでしょう。 皆を並べてワインに1,2,3...と順番をつけます。 ワインを飲んだ場合を●、飲まない場合を〇とすると、 1〇〇、 2〇●、 3●〇、 4●●、 と4つパターンがあります。なので2人だと誰が死ぬかで4本まで測ることができます。例えば、1番目の人が死んで2番目の人が生きていれば、3番目に振り分けられたワインが毒有りということです。 同じように3人だと、 1〇〇〇、2〇〇●、3〇●〇、4〇●●、5●〇〇、6●〇●、7●●〇、8●●●、 と8番まで測ることができます。 このように何人だといくつのパターンができるか、というのを書いていくと1人→2本、2→4、3→8、4→16、5→32、6→64、7→128、8→256、9→512、10→1024。 10人だと1024本まで測ることができます。なので10人で十分ということです。 よくこの問題が二進法で解けると解釈されるのは、有●、無〇という考えが二進法の1(有る)、0(無い)と同じだからです。つまり、何人いれば結果を知ることでワインの何番目まで分かることができるか、そういう問題です。