■既約性判定基準(その61)

16個の白と黒の真珠だけで、隣接する4つの真珠の白黒の組み合わせがすべて異なるネックレスを作ることができるだろうか?

そのような組み合わせは4^2=16通り存在するから、このネックレスは少なくとも16個の真珠をもたなければならないが、それは実際に可能だろうか?

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

16個の真珠をデザインするためにx^15+1の次数4の原始因数が必要になる。

その因数はx^4+x^3+1であり、これから漸化式

an+1=an+3+1が得られる。

初期条件a1=a2=a3=a4=1を用いると、漸化式から周期15の2項数列が得られる。

111101011001000;111・・・

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

1111010110010000

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

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

 このように16個の0と1からなる周回配列はド・ブリュインのサイクルと呼ばれる.

1111010110010000を反転させた

0000101001101111

または

0000100110101111も16通りすべての配列を作り出す.

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

 それでは4色のネックレス:

[Q]4つの異なる色(赤青黄緑)の真珠,計16個の組み合わせからなるネックレスで,隣接する2つの真珠の色の組み合わせがすべて異なるものを作ることができるだろうか?

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

[A]円周に沿って廻りながら,4色のうちから2色を選んだ対を{赤,青},{青,黄}のように隣り合う2つの記号が作る16通りの可能な配列が出てくるように塗ることができる.

2色の代わりにGF(4)上の多項式による設計に基づけば4つの異なる色からなるネックレスを作ることができるのである。

16個の真珠のネックレスは多くて4色の可能なすべての対をもつことができる

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