■白と黒の真珠のネックレス(その11)

 白と黒の真珠,計16個の組み合わせからなるネックレスで,隣接する4つの真珠の白黒の組み合わせがすべて異なるものを作ることができる.

 4つの真珠の白黒の組み合わせは2^4=16通りあるから16個の真珠は,最小限の個数であろう.白い真珠を1,黒い真珠を0とみて,実際にやってみると

1111

 1110

  1101

   1010

    0101

     1011

      0110

       1100

        1001

         0010

          0100

           1000

            0000

・・・・・

             0001

              0011

               0111

                1111

111101011001000;111・・・

周期の終わりを示すセミコロンに0を付加することによって

1111010110010000

に修正することができる.

===================================

このような16個の0と1からなる数列は「ド・ブリュージンのサイクル」と呼ばれる。1周回ってくると4つの0と1が作る可能な16通りの配列を作る出す。

どのようなサイズでもでも「ド・ブリュージンのサイクル」が存在することが、グラフ理論によって証明されている。

===================================