[趣味數學]趣談“九連環與格雷碼”

　　分析解九連環的完全記法，由于每次只動一個環，故兩步的表示也只有一個數字不同。下面以五個環為例分析。左邊起第一列的五位數是5個環的狀態，依次由第一環到第五環。第二列是把這個表示反轉次序的五位數，似乎是二進制數，但是與第四列比較就可以看出這不是步數的二進制數表示。第三列是從初始狀態到這個狀態所用的步數。最右邊一列才是步數的二進制表示。

　　00000－00000－0－00000

　　10000－00001－1－00001

　　11000－00011－2－00010

　　01000－00010－3－00011

　　01100－00110－4－00100

　　11100－00111－5－00101

　　10100－00101－6－00110

　　00100－00100－7－00111

　　00110－01100－8－01000

　　10110－01101－9－01001

　　11110－01111－10－01010

　　01110－01110－11－01011

　　01010－01010－12－01100

　　11010－01011－13－01101

　　10010－01001－14－01110

　　00010－01000－15－01111

　　00011－11000－16－10000

　　10011－11001－17－10001

　　11011－11011－18－10010

　　01011－11010－19－10011

　　01111－11110－20－10100

　　11111－11111－21－10101

　　我們發現，右邊一列數恰好是十進制數0到21的二進制數的格雷碼！ 這當然需要21步。如果把5位二進制數依次寫完，就是

　　10111－11101－22－10110

　　00111－11100－23－10111

　　00101－10100－24－11000

　　10101－10101－25－11001

　　11101－10111－26－11010

　　01101－10110－27－11011

　　01001－10010－28－11100

　　11001－10011－29－11101

　　10001－10001－30－11110

　　00001－10000－31－11111

　　這說明，對于只有5個環的五連環，從初始到狀態11111用的不是并不是最多，到狀態00001才是最多，用31步。類似，對于九連環，從初始到狀態111111111用的不是并不是最多，到狀態000000001才是最多，用511步。由于格雷碼111111111表示二進制數101010101，表示十進制數341，故從初始狀態到9個環全部上去用341步。這就是九連環中蘊涵的數學內涵。

　　注 由二進制數轉換為格雷碼：從右到左檢查，如果某一數字左邊是0，該數字不變；如果是1，該數字改變（0變為1，1變為0）。例，二進制數11011的格雷碼是10110.

　　由格雷碼表示變為二進制數：從右到左檢查，如果某一數字的左邊數字和是偶數，該數字不變；如果是奇數，該數字改變。

　　例 格雷碼11011表示為二進制數是10010.

　　以上可以用口訣幫助記憶：2G一改零不改，G2奇變偶不變。

　　例 設九連環的初始狀態是110100110，要求終止狀態是001001111，簡單解法與完整解法各需要多少步？過程如何？

　　解 初始狀態110100110，格雷碼是011001011，轉換為二進制數是010001101，相應十進制數是141.終止狀態是001001111，格雷碼是111100100，轉換為二進制數是101000111，相應十進制數是327.二者差326－141＝186，完整解法需要186步。

　　簡單解法步數，我們由141，327分別求相應的簡單步數，

　　對于N=141，得到N0=103；對于N=327，N0=242.二者差139，故簡單步數139.這個結果很容易在下一頁九連環電腦游戲上驗證。