先日、チューリングの計算理論入門という本を読んでいたら、『サンタクロースの汚れた靴下』という話が書かれていました。
どういう話かというと、1024個のプレゼントの箱のうち、間違えて一つだけサンタクロースの汚れた靴下をいれてしまったのでその箱を探さなければいけないというもの。どうやらその汚れた靴下は他のプレゼントと比べて重いらしく、ちゃんとしたプレゼントは全て同じ重さらしい。なので、天秤が下がれば汚れた靴下が入っている箱がわかるということだ。
ただし、1個ずつ比較していくと最大512回かかってしまいます。そこで、ある子どもの妖精が1024個を2つに分けて512個ずつを天秤にかけたらいいとのこと。そしたら、重いほうのグループに汚れた靴下が入ってると分かるため、さらにそれを2つに分けて、256個の2つのグループに、それを繰り返して、128→64→32→16→8→4→2→1というグループで比較していけば、10回の比較で終わるとのことだ。
でもこれ、比較回数だけを考えれば、2等分ではなく、3等分にすればもう少し少ない比較回数で見つけることができます。
つまり、1024個を3等分して、a.341個、b.341個、c.342個のグループに分ける。この時、数が同じ341個のグループのaとbを比較して、aが重ければaに、bが重ければbに、吊り合っていればcに汚い靴下があるということが分かりります。ここで、cにあると分かったとして、さらにそれを3等分してd.114個、e.114個、f.114個として先ほどと同じ要領でdとeを比較、dにあると分かったとして、g.38個、h.38個、i.38個に分け、gとhを比較してgにあると分かったとして、j.12個、k.13個、l.13個に分け、同じ個数のkとlを比較し、kにあると分かったとしてm.4個、n.4個、o.5個にわけmとnを比較、oにあると分かったとしてp.2個、q.2個、r.1個に分け、pとqを比較。pにあるとわかればその2つを比較して重いほうに汚い靴下が入っているということが分かる。
というわけで汚い靴下が入っていたグループは342→114→38→13→5→2→1と減っていくので、最大でも7回の比較回数ですむことが分かる。
ただ、これは飽くまで比較回数の話であって、3等分するという点は少し効率が悪いかもしれませんね。後、もしもう少し比較回数が少なくなるような方法があれば教えて下さい。
コメント