論理クイズの答えその2
こんにちは、田口です。
お待たせしました(?)論理クイズの残りの答えを載せます。今回長くなります(笑)
ここに1000本のワインがあって、1つは毒入りだということが分かっています。
毒入りのワインを1滴でも飲むと、10h~20h(正確な時間は分からないしワインによって異なる)で死にます。
今から24h以内に、自分の奴隷にワインを飲ませることで、どれが毒入りのワインかを判別したい。
毒入りのワインを特定するには最低何人の奴隷が必要か?
毒入りのワインは見た目や重さも他のワインと全く一緒です。
前提として、24h以内に分からないといけないということと、死ぬのが10h~20hの間ということで
時間差で奴隷に飲ませて判断させることと、同じ奴隷を使って何回も試す、といった手法が禁じられます。
正解は10人です。
解説すると、例えば奴隷が3人いるとして、この場合何本のワインを判別できるかを考えます。
奴隷A、奴隷B、奴隷Cとして、奴隷が死ぬ場合分けをすると
1.Aが死ぬ場合
2.Bが死ぬ場合
3.Cが死ぬ場合
4.A,Bが死ぬ場合
5.A,Cが死ぬ場合
6.B,Cが死ぬ場合
7.A,B,Cが死ぬ場合
の7通りです。
よって例えば、
ワイン1 | ワイン2 | ワイン3 | ワイン4 | ワイン5 | ワイン6 | ワイン7 |
A | B | C | A | A | B | A |
B | C | C | B | |||
C |
と飲ませることにより、判別可能となるのが分かるでしょうか。
この通りは
3C1+3C2+3C3=7通りと計算式で表せます。
つまり、最低の奴隷人数は
nC1+nC2+nC3…nCn≧1000
となるnが答えです。
nC1+nC2+nC3…nCn=2n-1
ですので、答えはn=10となります。
どうでしょうか。この問題はこのほかにも2進数的な考え方を使うことにより解く方法もあります。
ラスト1問も書こうと思いましたが長くなりそうなので今日はこの辺で^^