數學遊戲一筆畫

數學遊戲一筆畫

從最近一段時間發的推文來看，關於遊戲的話題，還是最受朋友們喜歡，因此，數學佬決定投大家所好，繼續介紹各種數學遊戲及其解法和原理。借著玩迷宮的威風，我又玩了一陣子小學生常玩的遊戲——一筆畫。

所謂一筆畫，就是一筆把一個圖形畫出來。例如下面是一個非常簡單的一筆畫題目。

 

其中的數字就是解法的路徑順序。當然解法不止一種，你完全可以走出不一樣的解答。

而下面則是一個稍難的一筆畫問題。

親愛的朋友，你可以試一試哦，不那麼容易的。

當然，也不那麼難，當年有個年輕人，輕鬆解決了這個問題，並據此寫成論文，這個年輕人叫歐拉，他寫的這篇論文叫《哥尼斯堡的七橋》，這篇論文開啟了一個數學分支。

當然，歐拉不會無聊地解一筆畫問題，他是在解決一個實際問題。哥尼斯堡有條河，河中央有兩個小島，為了方便居民往裡，一共建造了七座小橋，縱橫交錯，於是有不少人開始嘗試，能否不重複地走完所有的橋？

數學家歐拉首先很清晰地看到，解決這個問題絕不能自己親自去走，當然拉著女朋友去走也是解決不了問題，第一步就必須從實際問題中跳出來。所有的橋，其實我們一點也不關心是不是石頭橋是不是木頭橋，也不關心欄杆上雕著獅子還是猴子，甚至我們也不關心橋連著的是小島還是河岸。對吧，於是問題就轉變成

 

這個圖形中，是否能找到一條路徑，不重複走遍所有邊？

OK，偉大的歐拉還是沒有直接尋找這個問題的答案，而是想，如果能找到，那麼這個路徑應該具有什麼樣的特點？顯然，除了起點和終點，所有的中間點，都應該「只要有進就必須有出」，換言之，它們的邊必須是偶數。

好的，問題解決了。我們稱邊為偶數的點為偶數點，邊為奇數的點為奇數點，則

如果一個圖的所有點都是偶數點，那麼這個圖一定能一筆畫出，用任意一個點做起點和終點即可。

如果一個圖的奇數點是2個，那麼這個圖也能夠一筆畫出，用其中一個點做起點，另一個點做終點即可。

除此之外，奇數點不是0個或2個，這個圖無法一筆畫出。

而哥尼斯堡的七橋問題中，4個點都是奇數點，當然是無法一筆畫出了——答案居然是無解！

後來的研究加了個條件，這個圖首先得連著的，稱為連通圖。這個條件當然對，但是很無釐頭。

後來又有人研究了，說如果這個圖的奇數點有2n個，則它可以用n筆畫出。（好吧，正確，可以寫成論文，巴特，我認為沒有創意）

廢話不多說，我們已經知道了解一筆畫問題的關鍵：數點的邊。找出奇數點，沒有奇數點則任意點為起點，有2個奇數點則一個起點一個終點。中間的路徑很容易試，解法太多了。

 

在這個問題中，左右角的兩個點是奇數點，選其中一個做起點一個做終點，譁譁譁就解決了。什麼？怎麼走？深度優先搜索呀。很快的，幾乎不需要怎麼回溯。

在網上的遊戲中，為了增加難度，還設置了一些需要走兩次的線（要點：根本就可以忽略不計，因為走兩遍不就是回到原點嘛……），還有的設置一些單行線，（要點：這是真的障礙，因為單行線會大幅度減少解的個數），還有的設置了跳轉，（要點：自動跳轉就相當於一條邊而已）

小結：一筆畫問題，就是數一數每一個點的邊數。如果全部是偶數點，則從任意一點出發可以走一個圈回到出發點；如果兩個奇數點，則從其中一個點出發可以走一個鏈回到另一個奇數點。

長按下面的二維碼就可以關注我們哦！我們致力於讓您不討厭的數學

小技巧：點擊下面藍色小字「閱讀原文」，可以下載我寫的電子書哦。

http://pan.baidu.com/s/1qXGkvgS《老爸講水滸》

http://pan.baidu.com/s/1c1FUpqg《送給女兒的數學科普書》