魔術方塊中的數學原理.doc

《魔術方塊中的數學原理.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、魔術方塊中的數學原理台大數學系三年級張紘睿簡單的歷史介紹：魔術方塊是1974年，由匈牙利布達佩斯的建築系教授ErnoRubik發明的。本來的目的是為了讓學生瞭解立體結構所做的模型，為了區分每個小塊的移動，而分別把六面給上了不同的顏色，然後在稍微轉了幾下之後，發現這個東西非常的難復原，於是世界上第一個魔術方塊就誕生了。二階與三階的方塊：三階方塊（Rubik'sCube）是一般最常見的方塊，是由六個中心面（center），八個角(corner)，十二個邊(edge)所組成的。而二階的方塊（PocketCube）則是沒有中心面的方塊，只有三階方塊的八個角。

2、課堂上主要以這兩種類型來說明。首先，我們來看對於一個魔術方塊來說，它可以亂轉成幾種組合呢？全部的組合數：2階：7!x3^7（環排）3階：8!x12!x3^8x2^12（非環排）但是，所有的狀態都有可能出現嗎？或者說，如果我們把一個方塊拆開，再隨便裝回去，一定有辦法把它轉回原來的樣子嗎？答案是不行的。事實上，對於一個三階的魔術方塊來說，如果不把一顆魔術方塊給拆了，下面三種狀態是不可能出現的：(1)單對互換(exchangesinglepair)(2)單邊翻轉(flipsingleedge)，(3)單角自旋(twistsinglecorner)。現在，我

3、們就來說明這三種情形為什麼不可解，首先，我們要先說明的第一個東西是不變量，什麼是不變量？如果我們定義出一個函數，使得這個函數的值在變換之下仍然保持不變，那它就是一個不變量。舉例來說：孔明棋：　　　　　　　　　　　　３－puzzle　　　　　　　　　１２　３１　２３。。。　　　　　　　　　　　　　３　　２　　１。。。　　　　。。。　　　　　　　　　　　　１３　２１　３２　　　　　２　　３　　１(３，３，３)　　　　　　　　　　　在３－puzzle中一共有六種case，而其中只有三種有解，婐們稱之為偶至換(evenswap)而另外三種不可解的則稱為奇至換

4、(oddswap)，並不是所有的題目中奇至換都不可解，只是在這個例子中，剛好不可解。所以現在我們知道了，如果要用不變量來確認一個狀態和另一個狀態之間是否互通（就是可解的意思），我們可以先建構一個不變量的函數出來，然後計算它的值，再確認在合理的操做之下，這個值不會改變，那麼，我們就可以說如果有一個狀態，代入我們給出的公式計算，得到和原來不一樣的值，那這個狀態就不可解。現在，我們回到魔方上。對於下列的三種情形，現在我們分別給出三種不變量：單對互換：位置的不變量。單邊翻轉：邊的不變量。單角自旋：角的不變量。首先我們來看位置的不變量：這裡我們給出一個和３－p

5、uzzle相似的函數：為什麼是２０？因為我們有８個角和１２個邊，一共有２０個小方塊。經過計算可以知道，對於尚未轉亂的狀態來說f(X)=1而如果只有兩個方塊交換的時候f(X)=-1但是一個方塊最小的變換是對於單一個面做四分之一圈的旋轉，而在經過四分一圈旋轉之後f(X)=1。所以，我們可以知道不存在只有兩個單獨方塊對的交換。但是在二階的方塊中，只交換兩個方塊的情形是存在的，因為二階方塊沒有邊，所以它的變換是奇至換。接著，我們考慮邊和角的情形：對於每一個邊來說，有一面是1/2而有另外一面是0，而在每一個轉動中，每個面增加的總量是一個整數，減少的總量也是一個

6、整數，所以不存在只有一個邊翻轉的情形。對於每一個角來說，三面分別是０，1/3，2/3。則對於每一個旋轉來說，每個面的改變量一定是整數，而如果旋轉單一角，則會導致面的改變量是分數，所以單一角的旋轉也是不存在的。所以，實際上的組合數應該是：2階：7!x3^7/3=3,674,1603階：8!x12!x3^8x2^12/2/2/3=4,325,003,274,489,856,000圖論下的模型：如果我們把所有的狀態都當成一個點，而一個狀態可以經由一個旋轉達成另一個狀態的話，我們說這兩個點之間有邊。如此一來，我們會得到一個有4,325,003,274,489

7、,856,000個點的圖。為什麼要這樣模型化呢？因為這牽涉到一個相當複雜的問題：對於任意亂的方塊，是否存在一個最短路徑的解法？這個答案是肯定的，那麼如果存在一個這樣的解法，那麼將之推廣的話，對於所有的狀態，是否都能在n轉之內將其復元呢？事實上，這是一個NP-hard的題目，目前還沒有辦法用電腦計算出來，於是就有人把這個問題改成這樣的等價形式：對於這個圖中的任兩點，最長的距離是多少？不過這也只是一個想法而已，截至目前為止，仍然沒有人對這個問題做出解答。參考書目：１：C.Bandelow:InsideRubik’sCubeAndBeyond(Boston

8、:Birkhäuser,c1982)２：ErnőRubik:Rubik'scubiccompendium(O