天使問題是由英國數學家約翰·何頓·康威提出的一個博弈論問題[1],在2006年已獲解答。

圖中棋盤區域中央為天使,當天使力量為 3 時,其當前可移動區域被藍色點畫線圍起

陳述

編輯

天使問題是關於一個叫天使與惡魔的雙人遊戲,其規則如下:

  1. 兩名玩家分別扮演天使和惡魔
  2. 遊戲開始前,指定一個正整數 K,稱之為天使的力量
  3. 遊戲在一個無限大的方格棋盤上進行;開始時棋盤是空的,天使停留在棋盤上的某一個方格(稱為天使的起始點),惡魔並不存在於棋盤上
  4. 每一輪中,惡魔可以在棋盤上放置一個路障,路障不可以放置在天使停留處
  5. 每一輪中,天使可以向相鄰格移動至多 K 步,移動過程中可以穿過路障,但移動終點必須停留在沒有路障的格中;縱橫斜格均算作相鄰格
  6. 從惡魔開始,雙方交替進行(若從天使開始,從上面的規則描述,亦可等價轉換為從惡魔開始的局面)
  7. 若在一輪中,天使無法移動,則惡魔獲勝
  8. 如果天使能夠無限地繼續遊戲,則天使獲勝

天使問題可以陳述為:

是否存在某個K,使得力量為K的天使擁有必勝策略

已知的證明

編輯

二維

編輯
  • K = 1 時,惡魔有必勝策略(康威, 1982)
  • 如果天使不可以降低其 y 坐標,則惡魔有必勝策略(康威, 1982)
  • 如果天使一直增加它到起始點的距離,則惡魔有必勝策略(康威, 1996)

在2006年,有4位數學家獨立解決了天使問題。英國數學家布萊恩·鮑迪奇(Brian Bowditch) 證明了K = 4的時候,天使有必勝策略。[2] 挪威數學家Oddvar Kloster 和 András Máthé 各自證明了K = 2的時候,天使有必勝策略。[3][4]Péter Gács 則是證明了當 K 充分大時,天使有必勝策略。[5]

參考來源

編輯
  1. ^ John H. Conway, The angel problem頁面存檔備份,存於互聯網檔案館, in: Richard Nowakowski (editor) Games of No Chance, volume 29 of MSRI Publications, pages 3–12, 1996.
  2. ^ Brian H. Bowditch. The angel game in the plane (PDF). [2014-06-16]. (原始內容存檔 (PDF)於2016-03-04) (英語). 
  3. ^ O. Kloster. A Solution to the Angel Problem (PDF). [2014-06-16]. (原始內容 (PDF)存檔於2016-01-07) (英語). 
  4. ^ András Máthé. The Angel of power 2 wins (PDF). [2014-06-16]. (原始內容存檔 (PDF)於2016-10-13) (英語). 
  5. ^ Péter Gács. THE ANGEL WINS (PDF). [2014-06-16]. (原始內容存檔 (PDF)於2016-03-04) (英語). 

外部連結

編輯