はじめに

インターネットを徘徊していたときに偶然この問題を見つけ、OIの達人の助言とCSDNの助けを借りて、ようやく解法を思いつきました。

問題

あなたの目の前には、100本のシャッフルされた薬瓶があります。そのうち1本だけが毒薬です。あなたは7匹のネズミを持っています。毒薬を飲んだネズミは死にますが、そうでなければ死にません。この7匹のネズミを使って、ネズミの生死の状況から毒薬を見つける方法を設計してください。

各ネズミは無限の量の薬を飲めるものとし、各薬瓶が飲み尽くされることはないとします。この方法を実行している間、あなたは現在の実行状況を知ることはできません。つまり、前のネズミの生死に基づいてその後の操作を決めることはできません。

難しさ

この問題で最も難しいのは、すべての手順を完了した後にのみ結果を知ることができ、前のネズミの生死に基づいてその後の操作を決められないことです。

クラスメートと議論しているとき、皆は二分法を使って徐々に絞り込む方針に傾いていましたが、上記の難しさを考慮しないとしても、二分法だけでは、7匹すべてのネズミが死んでしまっても毒薬の瓶を見つけられない可能性が高いです。

この時点で、高校で習う通常の数学の方法ではこの問題を解くことができません。どうすればいいのでしょうか？

二進法

二進法はコンピュータの言語です。二進法について大まかに理解しましょう。

私たちが普段使っているのは十進法で、10になると桁上がりします。11番目の数を書くときは「11」と書きますが、これは十六進法で11番目の数を「a」で表すのと同じです。二進法も同様に、2になると桁上がりし、3番目の数を書くときは二進法で「11」と表します。

001 # 1
002 # 2
011 # 3
100 # 4
101 # 5

の後ろが十進数、#の前が二進数です。3桁に揃える方法を採用しており、1の左側の0は意味を持ちません。

二進法を理解したところで、問題を再度確認しましょう。7匹のネズミ、100本の薬瓶です。Pythonで二進数変換アルゴリズムを書き、1から100までのすべての数の二進数を列挙しました。

x=0
for i in range(0,100):
    x=x+1
    y = x
    b=""
    while(y>=1):
        b=str(num%2)+b
        num=num//2
    print(b)

100の二進数変換結果が1100100で、ちょうど7桁になることがわかりました。これは、100以前の数の二進数表現の桁数が7を超えることは決してなく、各十進数がただ1つの二進数に対応することを意味します。ちょうど7匹のネズミがいるので、この特性を利用して問題を解くことができます。

左から右へ7つの桁があり、各桁が1匹のネズミに対応します。対応する桁が1のとき、そのネズミはその薬瓶を飲みます。例えば、35番目の薬瓶を飲ませる場合、まず35に対応する二進数を計算し、7桁に揃えます。35番目の瓶に対応する二進数は0100011で、左から2桁目、6桁目、7桁目が1なので、2、6、7番目のネズミにそれを飲ませます。3匹すべてが死んだ場合、その薬が毒薬です。死ななかった場合や全滅しなかった場合は毒薬ではありません。なぜなら、これらのネズミは他の薬瓶も飲む可能性があり、判断できないからです。

解説はここまで。実践してみましょう。

実践シミュレーション

Excelを使って集計します。つまり表を作ります。Pythonの二進数アルゴリズムを使って1〜100のすべての二進数を求め、Excelにインポートします。7匹のネズミに番号を付け、対応する薬瓶を飲ませます。

84番の薬瓶が毒薬だと仮定して、シミュレーションを進めます。

グループ内のすべてのネズミが死亡したとき、そのグループが毒薬だと判断できます。つまり85番の瓶です。

視点を変えて考える

表を作成しているとき、数学的な思考を使わずに、これを生物の遺伝と見なすこともできることに気づきました。特定の遺伝子がすべて顕性遺伝子であるときにのみ、表現型が顕性になるという考え方です。しかし、二進法による解法が重要なポイントであることを理解すべきです。二進法がなければ、