帽子のパズル その３

下の説明だとHamming Codeがいまいちよく分からないので、ちょっと簡単に補足。

赤と青を０，１として、すべての帽子の組み合わせを０と１の列として考える。例えば、７人の囚人がいれば、２＾７通りの０と１の組み合わせがある。

この中のある部分集合を取りだして、その中の一つ一つの要素に対して、それ自体とそこから一つの数字をひっくり返した（０を１に、１を０に）ものを併せた集合を考える。これらが、全体をきれいに分割するとしよう。そのような部分集合がHamming Codeである。

例えば３囚人のケースなら、（０，０，０）と（１，１，１）がHamming Codeであり、（１，０，０）、（０，１，０）、（０，０，１）は前者に属し、残りは後者に属する。

さて、Hamming Codeが見つかったら、次のような戦略を考えることができる。

自分の数字を適当に選ぶことで、全体があるHamming Codeになるなら、そうならないような数字を選ぶ。そうでなければ、パス。

これは下に挙げた３人の場合の戦略を一般化したものになっている。この戦略に従うと、Hamming Codeが選ばれた場合は全員が間違え、それ以外が選ばれた場合は、一人が正解し残りがパスするということになる。（で、前にもいったように、n=2^m-1の場合はHamming Codeの割合（=確率）を1/n+1まで抑えることができる）。

こうしてみると、この問題が通信に関係していることも合点がいく。０と１で成り立っている情報が、ノイズのため、たまに一桁間違って伝えられることがあるとしよう。すると、Hamming Codeは、一桁のノイズが入っても元のコードを再現できるようなコードの集合になっている。二桁以上のノイズが入れば情報が正しく伝達されないが、ノイズの入り方が独立ならば、そのような確率は低いだろう。このように、Hamming Codeは正確な情報を安定して伝達する役割を果たしているというわけだ。