二進位蟲 - 拼圖

43
拋磚引玉一下

剛剛閒來沒事想說用暴力法畫出 N = 2~5 的 state diagram
在列出來之前要先說明一個大前提
就是說要得到全部0的A目標是以最少次數達到目標
阻止A的B自然也不會無緣無故幫助A更快達到目標

因為畫出完整的 state diagram 有些麻煩
所以我用下面的數列呈現

N = 2 00110
N = 3 0001110100
N = 4 0000111101100101000
N = 5 000001111101110011010110001010010000


-------------------------------------------------

下面解釋數列怎樣形成的

以 N = 3 為例 有 000, 001, 010, 011, 100, 101, 110, 111 8種可能


000 (end) | 000
001 > 000 (> 100 不合前提) | 001
010 | 010 < 101 (< 001 不合前提)
011 > 001 (> 101 不合前提) | 011
100 | 100
101 | 101
110 | 110 < 111 (< 011 不合前提)
111 > 011 (> 111 不合前提) | 111

化簡後

100
010 < 101
110 < 111 > 011 > 001 > 000

顯然 101 > 110 (> 010 loop 不合前提)
所以 010 < 101 > 110 < 111 > 011 > 001 > 000

最後 100 < 010 (< 110 不合前提)
結果便產生一個數列
100, 010, 101, 110, 111, 011, 001, 000

整理後
100
010
101
110
111
011
001
000
----------
0001110100

就是前面 N = 3 的數列

換句話說
N = 4 的數列 0000111101100101000 用另一種呈現方式就是
1000, 0100, 1010, 0101, 0010, 1001, 1100, 0110,
1011, 1101, 1110, 1111, 0111, 0011, 0001, 0000


-------------------------------------------------

從 N = 2 ~ 5 可以看到幾點有趣的現象:

1) 在大前提成立下 看不出有什麼可以阻止A勝出的方法

2) 第一項永遠都是 1000.....000 這大概就是讓A步數最多的解吧

3) 個人比較喜歡下面的呈現方式 雖然說還看不出有什麼規則就是...
1000 1100 1110 1111
0100 0110 0111
1010 1011 0011
0101 1101 0001
0010 0000
1001

附上 N = 5 的情形
10000 11000 11100 11110 11111
01000 01100 01110 01111
00100 10110 10111 00111
10010 01011 11011 00011
01001 10101 11101 00001
10100 11010 00000
01010 01101
00101 00110
00010 10011
10001 11001

4) 每組數字 0000 ~ 1111 都有出現在數列裡
總覺得這種數列應該很有名才對吧 但怎麼查都查不到


以上

--