補足 - 繰り返しのない列

[←]　[↑]　[→]

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

【答え】　存在する

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

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

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

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

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

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

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

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

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

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

0001011100...
000
001
010
101
011
111
110
100

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

◇

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

これはすぐわかる。

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

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

→頭はX0,X1以外

→X0,X1は途中にある

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

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

◇◇

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

(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)→stuと2つの道路を経由すればよい

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

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

◇◇◇

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

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

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

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

ビット長 n	輪の個数 2**(2^n-1 -n)	輪 (長さ2ⁿ)	町の列 (町の数2^n-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

[←]　[↑]　[→]