ベン図とグレイ符号 - フィボナッチ・フリーク

領域が4個のベン図を描きたい！

というのは誰もが一度は考えることだと思います（？）。しかし普通に描いてみると $2^4=16$ 通りすべての組み合わせができなかったり、同じ組み合わせの場所が2つできてしまったりと、なかなかうまくいきません。

f:id:fibonacci_freak:20171004115952p:plain

そこで今回は、領域がいくつのベン図であっても必ず機械的に書ける方法を紹介したいと思います！

使う数学的概念は「グレイ符号」というものです。

グレイ符号とは何か？

（※グレイ符号を知っている方はこの節は読み飛ばして構いません）

「符号」というのは数や文字列に対して別の数や文字列を対応させる規則のことです。ここではわかりやすく、2進列（0と1の並び）を別の2進列に変換する規則を考えます。

しかし、そもそもなぜ2進列を別の2進列に変換することなどを考えるのでしょうか。例えば実用的な話として、何かの棒の回転角度を検出するセンサーを作ることを考えてみましょう。基準となる位置から反時計回りに測った角度を $\theta$ として、

$0^\circ\leq \theta\lt 45^\circ\to 000,$

$45^\circ\leq \theta\lt 90^\circ\to 001,$

$90^\circ\leq \theta\lt 135^\circ\to 010,$

$135^\circ\leq \theta\lt 180^\circ\to 011,$

というように2進表記の $0,1,2,3,\dots$ の順番で信号が出力されるようにするのが普通でしょう。しかし実はこのような決め方では不具合が生じる可能性が高いのです。

たとえば棒の角度がちょうど $90^\circ$ 付近で動いている時、信号は $001$ と $010$ の間を行き来します。ここで各桁の信号が変化するタイミングが少しでもずれたら、その瞬間に $000$ や $011$ という全く別の信号が出力される可能性があるのです。これでは安定的な信号が得られません。

そこで同じく $45^\circ$ 区切りに、次の順番で信号が出力されるようにしてみます。

$000,001,011,010,110,111,101,100$

こうすれば信号が乱れることはありません。なぜなら隣り合う2つの信号は1桁しか違わないからです。実は $000,001,010,\dots$ にそれぞれ $000,001,011,\dots$ を割り当てるこの規則こそが、3桁のグレイ符号と呼ばれるものです。

具体的に作り方を定義しましょう。

$n$ 桁のグレイ符号とは,、 $0,1$ の列 $a_1\dots a_n$ に対し別の列 $b_1\dots b_n$ を対応させる規則であって、次のように帰納的に定義されるものである。
・ $1$ 桁のグレイ符号は $a_1=b_1$ （何もしない）。
・ $n$ 桁のグレイ符号は、 $b_1\dots b_{n-1}$ が $a_1\dots a_{n-1}$ に対応する $n-1$ 桁のグレイ符号で、末尾 $b_n$ は $a_{n-1}=a_n$ ならば $0$ 、そうでなければ $1$ 。

具体的には次のようになります。

f:id:fibonacci_freak:20171004123811p:plain

隣り合う自然数の2進表記に対応する符号は1桁しか違わないことが見て取れます。これは定義からただちに証明できます。実際 $a_1\dots a_{n-1}$ が変化するのは $n=a_1\cdots a_n$ （2進表記で自然数とみなす）が奇数から偶数になるときですが、末尾の2桁の差が変化するのは $n$ が偶数から奇数になるときで、これらは同時に変化することがないので帰納的に示せます。

領域が $n$ 個のベン図の描きかた

グレイ符号がわかってしまえば、実はベン図を描くのはとても簡単です。領域1個から初めて、次のように帰納的に描いていきます。 $n$ 個まで描けたとして、 $n+1$ 個目の領域を描きましょう。まず今あるベン図の $2^n$ 個の部屋に2進列を割り当てるのですが、上から $k$ 桁目は「その部屋が $k$ 番目に描いた領域の内部に入っているかどうか」を見て、入っていれば $1$ 、入っていなければ $0$ とします。たとえば $n=3$ なら次のようになります。

f:id:fibonacci_freak:20171004122854p:plain

全ての領域に2進列を割り当てたら、自然数 $0,1,2,\dots$ の2進表記に対応するグレイ符号の順番に線を結んで新しい領域を作ります。すると全ての部屋を1回ずつ通るので、全ての部屋が新しい領域で2分され、 $2^{n+1}$ 個の部屋からなる正しいベン図が書けるのです！グレイ符号を使ったのは、線を跨ぐごとに隣りあう部屋（=1桁のみ違う部屋）にしか行くことができないから、というわけです（領域を描いている途中で「飛び地」に行かなければいけない状況は、この作り方なら発生しません。気になった方は帰納法で示してみましょう）。