天使问题

天使问题是由英国数学家约翰·何顿·康威提出的一个博弈论问题[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) (英语). 

外部連結