2002/01/04 undo
今日、フジテレビで「平成教育委員会スペシャル」が放送されていた。そこで面白い問題が出ていたので紹介しておきます。そのままじゃぁなんなので少しアレンジしますけど、答えを知っている人には同じ問題にしかみえませんよ！
ここの6つの箱があります。箱の中にカプセルがたくさん入っています。カプセルの中には水か無色無臭の液体の毒だけが入っています。毒を飲めば死んでしまいます。また水を飲まなくても死んでしまいます。どのカプセルに毒が入っていて、どのカプセルに水が入っているのかは分からなくなってしまいました。
分かっていることは、水の入っているカプセルは100gであるが、毒の入っているカプセルは101gであること、同じ箱の中のカプセルは中味も同じということだけです。ここではカプセルの質量を1g単位で測ることしかできません。ただし、1度に何個でも測ることができます。どのように何回測れば、毒と水を判別することができるでしょうか？ 最少回数は何回でしょうか？
まず、箱に、A,B,C,D,E,Fという名前をつけましょうか。
Aから1カプセル取り出して、測れば、Aが水か毒か判定できます。これを6回繰り返せば、すべてを判定することができますね。おそらくこれが一番単純な方法でしょう。この方法の1回の測定で得られる情報は、その箱の中が水か毒かの2値です。これを6回得るだけで判別できることが分かります。
では、A, B両方の箱から1カプセルずつ取り出して、1度に測定すると、どうでしょうか？
両方とも水であるか、両方とも毒であるか、どちらか片方が毒であるかの3値の情報を得ることができます。同じ1回の測定で得られる情報が増えました(^_^)
偶然、両方とも毒か水であれば、最初の方法よりも少ない手順で判定できるのですが、その確率は2分の1です。片方が毒だと分かった場合、どちらかを測定しなければ、どちらが毒であるのか特定することはできません。この場合は最初の方法と大して違いません。
では、A, B, C３つの箱から1カプセルずつ取り出して、1度に測定すると、どうでしょうか？
この場合、3つとも水であるか、2つが水であるか、1つが水であるか、すべて毒であるかの4値の情報を得ることができます。しかし、1回で判定できる確率は4分の1にしかなりません。
同様にして、2つもしくは1つが水であった場合、これを判別するためには別の方法で測らなければなりません。1回めの測定で得られた情報は多いのですが、回数については最初の方法とあまり違わないことが分かります。
これ以上、増やしても、同様です。
今度は、Aから1カプセル、Bから2カプセル取り出して、1度に測定すると、どうでしょうか？
両方とも水、両方とも毒、Aだけ水、Bだけ水の4値の情報を得ることができることが分かるでしょうか？
1回めの測定で得られる情報は、解3と同じで4値の情報です。しかし、決定的に違うことは、解4ではこれを3回繰り返すことで、すべての情報を得られるということです。
最初に戻りましょう。解1より、最終的に得る情報は、2値の情報を6回です。解4より、4値の情報を3回と言い換えても良いでしょう。つまり、すべてを判定することは、2の6乗=4の3乗=64とおりの可能性から1つに絞りこむことになります。
もう答えは分かったことと思いますので解説はやめます :-p
私が言いたいのは、情報量や2進数をせっかく習っても、こういう思考が数秒くらいで出てこないようだと話にならない！ということです。プログラマにとっては、そのくらい常識的な知識なのです。