無法解決的「14-15難題」

無法解決的「14-15難題」
Photo Credit: Shutterstock / 達志影像
我們想讓你知道的是

「14-15難題」曾經風靡一時,但其實是無法解決的難題,我們可以用數學證明。

唸給你聽
powered by Cyberon

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

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

15_puzzle4

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

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

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

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

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

15_puzzle
  • 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又會如何變化呢?

15_puzzle2

參考上圖,如果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的變化都是偶數,一個奇數無論加或減多少個偶數都只會是奇數,變不出偶數,所以洛伊德提出的難題不可能破解。

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

本文獲授權轉載,原文見作者網誌

相關文章︰

責任編輯︰Kayue
核稿編輯︰Alvin