こんな問題がありました。
一滴でも飲むと20時間後に死ぬ毒が、1000本のワインのうち1本にだけ入っている。
奴隷に飲ませて、24時間以内にどれが毒入りか調べるとき、奴隷は何人必要か。
なかなか物騒ですが、そのことには触れません。
もし時間的制約がなければ、奴隷1人に片端から1日に1本ずつ飲ませればいつか分かるので答えは「1人」です。
時間的制約を考えるとまず思いつくのは奴隷1000人に1本ずつ飲ませる方法。これならば確実ですが、もっと効率の良い方法があります。答えは「10人」です。
解答例
ワインに番号を付ける。番号を2進数10桁で表わす。
0001番「0000000001」
0002番「0000000010」
0003番「0000000011」
0004番「0000000100」
0005番「0000000101」
：
0399番「0110001111」
0400番「0110010000」
0401番「0110010001」
：
0998番「1111100110」
0999番「1111100111」
1000番「1111101000」
奴隷が10人いるとする。
1の奴隷は2進数の下1桁目が「1」となっているワインを飲む。
2の奴隷は2進数の下2桁目が「1」となっているワインを飲む。
：
10の奴隷は2進数の下10桁目が「1」となっているワインを飲む。
奴隷が10人いれば1000番までのワインについて全パターンを過不足なく網羅できる。
一口ずつ飲む必要はなく、自分のグラスに一滴ずつ入れ、それを飲む。
飲んでから20時間後にどの奴隷が死んだかを調べ、該当するワインを探す。
例えば、5の奴隷、8の奴隷、9の奴隷が死に、他が生きていれば「0400番」のワインが該当する。
一般化
ワイン1本ならば「1人」。
ワイン2本ならば「1人」。
1本だけ飲んで生死で判定できる。
ワイン3本ならば「2人」。
1番を1の奴隷が飲み、2番を2の奴隷が飲む。2人とも死ななければ3番と分かる。
ワイン4本ならば「2人」。
1番と3番を1の奴隷が飲み、2番と3番を2の奴隷が飲む。
1の奴隷だけが死ねば1番と分かる。
2の奴隷だけが死ねば2番と分かる。
2人とも死ねば3番と分かる。
2人とも死ななければ4番と分かる。
ワイン5本ならば「3人」。
1の奴隷は1番と3番と5番を飲む。
2の奴隷は2番と3番を飲む。
3の奴隷は4番と5番を飲む。
1の奴隷だけが死ねば1番と分かる。
2の奴隷だけが死ねば2番と分かる。
3の奴隷だけが死ねば4番と分かる。
1と2の奴隷が死ねば3番と分かる。
1と3の奴隷が死ねば5番と分かる。
このようにしていくと、奴隷がx人で判定できるワインはy本とすると
y=2^x
と表せることが分かる。
ワイン1000本の場合は
1000=2^x
log(1000)=log(2^x)=x*log(2)
x=log(1000)/log(2)=9.966
切り上げて「10人」。
コメント