不可還原的拼圖介紹
現在很多手機和電子詞典上都有這款遊戲,不知到大家在玩的時候有沒有發現有的拼圖怎麽都還原不到完整的圖片(或數字順序),最終出現有1對板塊(兩個)是對調的,這個時候妳可以停下來了,這不是妳水平的問題,是遊戲設計者的過錯!很多遊戲設計者都是將板塊隨機打亂,實際上並不是所有隨機打亂之後都是可以還原的!確切的說,隨機打亂後,有二分之壹的概率是可以被還原的。詳細證明如下:
b圖
假設圖中的a是3*3數字拼圖標準的結果,則對於圖b的狀態是不可能變換成a的。證明起來需要用到高等代數裏逆序數的概念,具體的說是用到了壹個簡單的定理。
定義:在壹個1,2,...,n的排列中,如果壹對數的前後位置與大小順序相反,即前面的數大於後面的數,那麽它們就稱為壹個逆序。壹個排列中逆序的總數就稱為這個排列的逆序數。逆序數為偶數的排列稱為偶排列;逆序數為奇數的排列稱為奇排列。如2431中,21,43,41,31是逆序,逆序數是4,為偶排列。——這是北大《高等代數》上的定義。
定理:交換壹個排列中的兩個數,則排列的奇偶性發生改變。(證明見任何壹本《高等代數》)
我們將空格看成數字9(數字9對應空位),按正常順序看a圖,9個數字排列是123456789,其逆序數是0,是偶排列;b圖是123456879,逆序數是1,是奇排列。我們知道,我們能夠移動空塊相鄰的塊,這裏的移動相當於壹種特殊的對換(相鄰對換),例如:對於b圖,移動6就相當於9和6互換(9向上移動了),移動7就相當於9和7互換(9向左移動了)。現在假設從b圖經過壹系列的平移變到了a圖,則空格塊9必然移動(對換)了偶數次(向左壹次必然要再向右壹次回來,向上壹次必然要向下再回來,最終才能夠回到右下角的位置),根據上面的定理最終變成的排列必然是仍然是奇排列(和b相同),然而a圖是偶排列,因而產生矛盾,因此b圖不可能通過平移變成最終的a圖。
呵呵? 采納吧