解謎遊戲

棋盤開車

在有速度限制的棋盤道路網中,你如何找到最快速的路線,到達目的地?

撰文/夏沙(Dennis E. Shasha)
翻譯/翁秉仁

解謎遊戲

棋盤開車

在有速度限制的棋盤道路網中,你如何找到最快速的路線,到達目的地?

撰文/夏沙(Dennis E. Shasha)
翻譯/翁秉仁

有一個棋盤道路網,共有六條間隔10公里的南北向道路,跨在六條間隔10公里的東西向道路上(如下圖)。每個交叉口都有進出的交流道相互連結,由於沒有紅綠燈,我們假設從南北向道路轉到東西向道路(相反也一樣)不花時間。這個路網車流量不大,不過交通警察對超速倒是抓得很勤。


路網的速限規定很奇特,最南端的東西向道路速限是時速10公里,往北一條東西向道路的速限是時速20公里,以此類推,一直到最北端的東西向道路是時速60公里。南北向道路的速限也類似,從最西端南北向道路的時速10公里,一直到最東端的時速60公里。我們用行數和列數來標記道路交叉口,(1, 1)是西南角的交叉口,東南角是(6, 1),西北角是(1, 6),依此類推。



【暖身題】

請找出從(1, 1)到(6, 3)的最快合法路徑。 結果,最快的路徑不只一條,其中一條是花1小時從(1, 1)到(2, 1),再開1小時走到(2, 3),最後直奔(6, 3),要再加1小時20分。在相同距離的路徑裡,最慢的一條是先花5小時從(1, 1)開到(6, 1),再用20分開到終點。


【暖身題答案】

紅色路徑是暖身題的一個解,黃色路徑雖然距離相同,但是最慢的走法。用什麼走法可以最快走完所有交叉口?


【進階題】

從(1, 1)開始,請用最短的時間走過所有的交叉口。如果想要用更短的時間走完所有交叉口,是不是有比較好的起點呢?我猜是沒有,不過,我想看看有沒有聰明的證法,畢竟數學是猜想很容易就會猜錯的。


【進階題答案】

下圖為其中一個解答,一共走了12小時5分鐘



【欲閱讀更豐富內容,請參閱科學人2004年第26期4月號】