【偶数奇数】パリティビットとは？クイズで意味解説【parity】

こんにちは。タクマ™ [@suwaru_blog] です。

前回、余剰について解説しました。

数字を 2 で割ったときの余剰が 0 か 1 かによって、
偶数・奇数の判定ができると書きましたが、「偶奇」にはどんなメリットがあるのでしょうか？

【クイズ①】オセロで通信

手品師・弟子・客の 3 人がいます。
手品師は目隠しをしています。

テーブルに裏表ランダムのオセロが 7 個並んでいます。
手品師は色を見ることがきません。

弟子はオセロを 1 つ追加します。

客は 8 個のオセロを 1 つだけ裏返すか、何もしない行動をとることができます。

手品師が 1 つだけ裏返したか、何もしなかったか、見破るにはどうしたらいいでしょうか？

答え

弟子はオセロが 7 個の時点で「黒」の数を数えます。
そして「黒」の偶奇によって、追加するオセロの色を決めます。

このルールを適用すると、常に 8 個のオセロの「黒」の数は「偶数」で保たれます。
この先、客が取れる行動は以下 3 つです。

手品師は、黒が「奇数」だったら「裏返した」と回答すればいいし、
黒が「偶数」だったら「何もしなかった」と回答すればよいことになります。

パリティとは (パリティのチェック)

このクイズはコンピュータ通信でいうところの「バリティ」で説明することができます。
パリティ (偶奇) とは、データが途中でおかしくなっていないかチェックする仕組みです。

二進法を使うと、オセロの白は「0」で、黒は「1」にあたります。
手品師は「受信者」で、弟子は「送信者」で、客は「通信を乱す雑音(ノイズ)」といえます。

※ 二進法については以下の記事で解説しています

バリティ・ビット

受信者はパリティを調べることで、ノイズで通信エラーが起きたか判定できます。

偶数だったらエラーはない、もしくは、奇数だったらエラーはない…
どちらのルールを適用するかは「送信者と受信者の間で決定」します。

バリティ・ビットで 2 つの集合に分割

7 個のオセロの並べ方は 2^7 で 128 パターンあります。
そのうち 64 パターンは黒が「偶数」、残りの 64 パターンは黒が「奇数」になります。

つまり 128 パターンを 2 つのグループに分けることができます。

弟子が追加するオセロは、どっちのグループに属しているかを表す「目印」ともいえます。
これはオセロが「黒か白か」 2 パターンの置き方しかないので 2 つのグループに大別できるのです。

【クイズ②】恋人探し

ある小さな国には A, B, C, D, E, F, G, H という 8 つの村があります。
村と村は次のように繋がっています。

あなたの恋人は 8 つの村のどこかにいますが 1 ヶ月ごとに隣の村に移動します。
(たとえば G の村にいるなら、来月は C, F, H いずれかの村に移動します)

恋人が 12 ヶ月前は G の村にいた…という情報だけ持っている場合、
今月、恋人が A の村にいる確率はいくつでしょう？

答え

表にすると答えはシンプルです。

恋人がどの村に向かうかはランダムなので、村の「道筋」をすべて検討するのは大変です。
なので、たどり着く可能性のある村だけを洗います。

12 回目の移動は偶数回目なので A にいる可能性は 0 といえます。

奇数村・偶数村の 2 つのグループに分けられることに気づけるか？…がポイントです。
現在、どの村にいるかまでは分かりませんが、奇数村・偶数村どっちにいるかは判定できます。

常に「偶数村からの移動先は奇数村で、奇数村からの移動先は偶数村」になるので、
こうしたパリティ (偶奇) のチェックが適用できます。

【クイズ③】畳の敷き詰め

以下の部屋全体 (62半畳) に畳 (1畳) を敷き詰めることはできるでしょうか？

答え

1 畳は 2 半畳 で「偶数」です。また、部屋全体も 62 半畳の「偶数」です。
お互い偶数なので、敷き詰められる可能性はありそうです。

ここで部屋と畳を「白黒」の半畳で塗り分けてみましょう。

数えると、黒の半畳は 30 個・白の半畳は 32 個です。

1 畳は「黒の半畳」と「白の半畳」で構成されているため、
部屋の黒と白は同数じゃないと敷き詰めるとことはできません。

従って、部屋を畳で敷き詰めることは不可能です。

パリティを使って考える

計算する場合、黒の半畳に「+1」白の半畳に「-1」を割り当てます。

可能性がある…という点に注意してください。
これは論理の「逆」なので、条件が入れ替わったからといって「真」になるとは限りません。

※ 論理については以下の記事で解説しています

今回の場合は 30 - 32 = 2 なので敷き詰めることはできない、と証明できます。

できないことを証明するのは簡単

パリティのチェックで NG がでると、「できない」ことの証明は簡単です。
試行錯誤して検証する必要がなくなります。

CS シリーズ

次回

前回