15方塊數字推盤遊戲難題

來源：My Puzzle Collection

大家都應該玩過這種15方塊數字推盤遊戲吧？板上會有15個標記了1至15號的方塊和一個空格，玩家可以把方塊移向空格，從而改變次序。遊戲的最終目標是要把15個數字依次排序好，並且最後一個格子為空位。

一位大力推廣遊戲的謎題設計者洛伊德（Samuel Loyd）就曾提出過一個「14-15難題」，就是把15方塊數字推盤遊戲中的14和15號方塊對調，其他方塊依次序排好，最終目標就是把15個數字排好。他更提出供了一筆1000美元的獎金去獎勵首位解到的人。

據聞那時候，這遊戲風靡一時，街上行人都拿著小推盤在解謎。其風靡程度應該就好像幾年前大家都拿著電話在街上捉精靈一樣。無數的挑戰者都嘗試破解難題，但都失敗而回。大家都可以試試破不破解到。

群眾經過一段長時間都解不到，開始有人懷疑根本上就不可能把方塊還原成數字依次排序的模樣。但如何證明呢？這時候數學就大派用埸了。

要分析這問題，最傳統最典型的方法是利用抽象代數（abstract algebra）中置換群（permutation group）的理論去分析轉置（transposition）的數量。方法其實很簡潔很易懂，不過始終需要較多背景知識。為了令廣大讀者都看得懂，史丹福不如在此介紹一個更基礎的，初中學生都懂的方法去研究這個難題。

設第一行由左至右4個位置分別是1號至4號，第二行由左至右4個位置分別是5號至8號，如此類推，我們共有16個位置。1至15號的方塊散落在這16個位置中。我們的最終目標是15塊方塊由小至大排好在相對應的位置中。

我們移動方塊時會打亂方塊的排列，有些較小的方塊卻「打尖」地進駐了一個比較大的方塊後的位置，我們將分析方塊「打尖」的情況。例如在下圖中：

1號方塊打了4塊方塊（2、6、3及13號）的尖；
2號方塊佔了最前的位置，沒有打到任何尖；
3號方塊打了1塊方塊 （6號）的尖（留意，3號方塊是應該在2號後的，所以不算打了2號方塊的尖）；
4號方塊打了4塊方塊 (6、13、10及12號）的尖，如此類推。

我們設所有方塊打尖數量的總和為m。 我們每次移動方塊時，其實都可以想像成移動空格。如果空格向左或者向右行的話，不影響方塊打尖的數量，所以m維持不變。

我們再設空格所在的行數為n。

如果空格向上一行，n會減1。m又會如果變化呢？

參考上圖，如果A少於B、C、D的話，方格向上令A 號方塊打了B、C、D號方塊的尖，m會加3。

如果A少於B、C、D中的其中兩個（設是B與C）的話，空格向上令A號方塊打了B與C號方塊的尖，但值得留意的是D號方塊原本打了A號方塊尖，現在卻不再打尖了，所以A 號方塊的打尖數加2，D號方塊的打尖數減1，m是總打尖數，就會加1。

如果A少於B、C、D中的其中一個，空格向上令m減1；如果A大於B、C、D，空格向上令m減3。

大家留意到甚麼？有沒有發現m的變化永遠是奇數？另外，空格向上左一行，n會減1，因此m+n的總變化量必為偶數。大家可以試試想一下空格向下的情況，同樣地每行一步的m+n變化量必為偶數。

洛伊德提出的「14-15難題」中，m是1（只有14號方塊打了15號尖），n是4（空格位於第4行），m+n是5，是奇數。我們最終目標是m是0，n是4 ，m+n是4，是偶數。但無論我們如何走，m+n的變化都是偶數，一個奇數無論加或減多少個偶數都只會是奇數，變不出偶數，所以洛伊德提出的遊戲是不可能做到的。

所謂「全心探討數學，明道理答案終會找到」，其實只要細心分析，會發現不少的遊戲都有數學隱藏在其中，奧妙不已。