1000本から毒入りワインを見つける問題

Pocket

こんな問題がありました。

一滴でも飲むと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番」のワインが該当する。

0400番「0110010000」

一般化

ワイン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人」。

[ 2014年3月21日 | カテゴリー: 小ネタ | タグ: ]

« | »

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

送信してください。


タグ

カテゴリー

最近の投稿

最近のコメント

固定ページ

アーカイブ

stabucky

写真

メタ情報