補足 - 繰り返しのない列

[] [] []


【問題】 すべてのnビット列が1回ずつ登場する列(完全な列とよぶ)は存在するか?

【答え】 存在する

(1)    nビット列は2 n種類しかないから、完全な列の長さは2n + (n-1)

(2)    完全な列では、頭の(n-1) ビットと尾の(n-1) ビットは重なる。したがって、頭と尾の(n-1) ビットを重ねると長さ2 nの輪になる

(3)    nビット列を一方通行の道路、2つのビット列の重なりの(n-1) ビットを町と見なす。すると列は道路を町でつないだルートになる

例) pqrsは、pqr→(qr)→qrs

したがって 「完全な列」とは「すべての道路を一回ずつ通るルート」のこと

(4)    どの町も2本の道が入り、2本の道が出ている。つまり入ったら必ず出られる

(5)    どの道路からどの道路へも必ず行ける。つまりすべての道路はつながっている

(6)    「すべての道路を一回ずつ通るルート」は任意のnについて必ず存在する

(7)    さらにその個数は2**(2n-1-n)らしい

すべてのnビット列が1回ずつ登場する列とは、例えば次のように先頭からスライドしながら3ビットずつ抜き出すと全ての3ビット列が1回ずつ登場する列のことである。

0001011100...

000

 001

  010

   101

    011

     111

      110

       100

「数学ができる人はこう考える」(シャーマン・スタイン)に、この列の話が載っている。本では、素朴な数え上げから始めてだんだんと洗練された方法を見つけていく過程がテーマになっており、問題と解答、定理と証明を羅列した教科書と違って、なるほど数学ができる人はこういう風にやるのかと分かった気にさせてくれる。ただ、本稿ではM系列に似たこの系列の性質だけ紹介する。

(1)    nビット列は2 n種類しかないから、完全な列の長さは2n + (n-1)

これはすぐわかる。

(2)    完全な列では、頭の(n-1) ビットと尾の(n-1) ビットは重なる。したがって、頭と尾の(n-1) ビットを重ねると長さ2 nの輪になる

もし頭の(n-1) ビットが、尾の(n-1) ビット(これをXとおく)と異なるとすると、

頭はX0,X1以外

→X0,X1は途中にある

→1X0,0X0,1X1,0X1も途中にある

尾は0X1Xなのでこれらと重なってしまうので矛盾

◇◇

ここで少し天下り的になるが、列を道路網と見なす。

(3)    nビット列を一方通行の道路、2つのビット列の重なりの(n-1) ビットを町と見なす。すると列は道路を町でつないだルートになる

例) pqrsは、pqr→(qr)→qrs

したがって 「完全な列」とは「すべての道路を一回ずつ通るルート」のこと

(4)    どの町も2本の道が入り、2本の道が出ている。つまり入ったら必ず出られる

 町Xに入ってくる道は0X,1X、出ていく道はX0,X1

(5)    どの道路からどの道路へも必ず行ける。つまりすべての道路はつながっている

道路pqrから任意の道路stuへ行くにはpqr→(qr)→qrs→(rs)→rst→(st)→stu2つの道路を経由すればよい

(6)    「すべての道路を一回ずつ通るルート」は任意のnについて必ず存在する

上記(4)より、途中の町で行き止まりになることはないし、スタートした町は終点でもある。さらに(5)より、ルートは一筆書きできる。もし、あるルートで終点に戻ってきたときに、まだ通ってない道路があったとしたら、そこは寄り道で通ればよい。この寄り道は必ずできる。なぜなら、もし途中の町で、それまで通って来た町に出入りする道路をすべて通っていたとしたら、その道路網だけで完結していることになり、その町からまだ通ってない道路へ行けないことになるが、これは(5)に反する。結局、任意のnについて「すべての道路を一回づつ通るルート」は存在する。

◇◇◇

(7)    さらにその個数は2**(2n-1-n)らしい

これはどうやれば示せるのかわからなかった。

n=5のとき輪の個数は211=2048になるらしいので書き出せないが、n=4以下のときを書き出してみた。

輪の(1')等は(1)の逆方向(左右反転)になっていることがわかるが、輪を見ていてもそれ以上の規則性は見いだせないので、町(n-1ビット)16進表記して町の列も書き出してみたが、輪の個数を導くような規則性は見いだせなかった。

ビット長

n

輪の個数

2**(2n-1 -n)

(長さ2n)

町の列

(町の数2n-1)

道路網

2

1

(1)0011

(1)0011

3

2

(1)00010111

(1')00011101

(1)00121332

(1')00133212

4

16

(1)0000100110101111

(2)0000100111101011

(3)0000101001101111

(4)0000101001111011

(5)0000101100111101

(6)0000101101001111

(7)0000101111001101

(8)0000101111010011

(1')0000111101011001

(2')0000110101111001

(3')0000111101100101

(4')0000110111100101

(5')0000101111001101

(6')0000111100101101

(7')0000101100111101

(8')0000110010111101

(1)0012413652537764

(2)0012413776525364

(3)0012524136537764

(4)0012524137765364

(5)0012536413776524

(6)0012536524137764

(7)0012537764136524

(8)0012537765241364

(1')0013776525364124

(2')0013652537764124

(3')0013776536412524

(4')0013653776412524

(5')0012537764136524

(6')0013776412536524

(7')0012536413776524

(8')0013641253776524

 



[] [] []