ベン図とグレイ符号
領域が4個のベン図を描きたい!
というのは誰もが一度は考えることだと思います(?)。しかし普通に描いてみると通りすべての組み合わせができなかったり、同じ組み合わせの場所が2つできてしまったりと、なかなかうまくいきません。
そこで今回は、領域がいくつのベン図であっても必ず機械的に書ける方法を紹介したいと思います!
使う数学的概念は「グレイ符号」というものです。
グレイ符号とは何か?
(※グレイ符号を知っている方はこの節は読み飛ばして構いません)
「符号」というのは数や文字列に対して別の数や文字列を対応させる規則のことです。ここではわかりやすく、2進列(0と1の並び)を別の2進列に変換する規則を考えます。
しかし、そもそもなぜ2進列を別の2進列に変換することなどを考えるのでしょうか。例えば実用的な話として、何かの棒の回転角度を検出するセンサーを作ることを考えてみましょう。基準となる位置から反時計回りに測った角度をとして、
というように2進表記のの順番で信号が出力されるようにするのが普通でしょう。しかし実はこのような決め方では不具合が生じる可能性が高いのです。
たとえば棒の角度がちょうど付近で動いている時、信号はとの間を行き来します。ここで各桁の信号が変化するタイミングが少しでもずれたら、その瞬間にやという全く別の信号が出力される可能性があるのです。これでは安定的な信号が得られません。
そこで同じく区切りに、次の順番で信号が出力されるようにしてみます。
こうすれば信号が乱れることはありません。なぜなら隣り合う2つの信号は1桁しか違わないからです。実はにそれぞれを割り当てるこの規則こそが、3桁のグレイ符号と呼ばれるものです。
具体的に作り方を定義しましょう。
・桁のグレイ符号は(何もしない)。
・桁のグレイ符号は、がに対応する桁のグレイ符号で、末尾はならば、そうでなければ。
具体的には次のようになります。
隣り合う自然数の2進表記に対応する符号は1桁しか違わないことが見て取れます。これは定義からただちに証明できます。実際が変化するのは(2進表記で自然数とみなす)が奇数から偶数になるときですが、末尾の2桁の差が変化するのはが偶数から奇数になるときで、これらは同時に変化することがないので帰納的に示せます。
領域が個のベン図の描きかた
グレイ符号がわかってしまえば、実はベン図を描くのはとても簡単です。領域1個から初めて、次のように帰納的に描いていきます。個まで描けたとして、個目の領域を描きましょう。まず今あるベン図の個の部屋に2進列を割り当てるのですが、上から桁目は「その部屋が番目に描いた領域の内部に入っているかどうか」を見て、入っていれば、入っていなければとします。たとえばなら次のようになります。
全ての領域に2進列を割り当てたら、自然数の2進表記に対応するグレイ符号の順番に線を結んで新しい領域を作ります。すると全ての部屋を1回ずつ通るので、全ての部屋が新しい領域で2分され、個の部屋からなる正しいベン図が書けるのです!グレイ符号を使ったのは、線を跨ぐごとに隣りあう部屋(=1桁のみ違う部屋)にしか行くことができないから、というわけです(領域を描いている途中で「飛び地」に行かなければいけない状況は、この作り方なら発生しません。気になった方は帰納法で示してみましょう)。
最後にこうして描ける領域6個(部屋は個)のベン図を鑑賞して終えることにしましょう。
楽しい!(*^^*)