フィボナッチ・フリーク

数学の小ネタ集。

Fibonacci Freak

ベン図とグレイ符号

領域が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付近で動いている時、信号は001010の間を行き来します。ここで各桁の信号が変化するタイミングが少しでもずれたら、その瞬間に000011という全く別の信号が出力される可能性があるのです。これでは安定的な信号が得られません。

そこで同じく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_na_{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桁のみ違う部屋)にしか行くことができないから、というわけです(領域を描いている途中で「飛び地」に行かなければいけない状況は、この作り方なら発生しません。気になった方は帰納法で示してみましょう)。

最後にこうして描ける領域6個(部屋は2^6=64個)のベン図を鑑賞して終えることにしましょう。

f:id:fibonacci_freak:20171004125757p:plain

楽しい!(*^^*)