天使问题 - 维基百科,自由的百科全书
此條目需要擴充。 (2014年6月16日) |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/31/Angel_problem.svg/200px-Angel_problem.svg.png)
天使问题是由英国数学家约翰·何顿·康威提出的一个博弈论问题[1],在2006年已獲解答。
陳述
[编辑]天使问题是關於一個叫天使與惡魔的雙人遊戲,其規則如下:
- 兩名玩家分別扮演天使和惡魔
- 遊戲開始前,指定一個正整數 K,稱之為天使的力量
- 游戏在一个无限大的方格棋盘上进行;开始时棋盘是空的,天使停留在棋盘上的某一个方格(称为天使的起始点),恶魔并不存在于棋盘上
- 每一轮中,恶魔可以在棋盘上放置一个路障,路障不可以放置在天使停留处
- 每一轮中,天使可以向相邻格移动至多 K 步,移动过程中可以穿过路障,但移动终点必须停留在没有路障的格中;纵横斜格均算作相邻格
- 从恶魔开始,双方交替进行(若从天使开始,从上面的规则描述,亦可等价转换为从恶魔开始的局面)
- 若在一轮中,天使无法移动,则恶魔获胜
- 如果天使能够无限地继续游戏,则天使获胜
天使問題可以陳述為:
是否存在某個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]
參考來源
[编辑]- ^ John H. Conway, The angel problem (页面存档备份,存于互联网档案馆), in: Richard Nowakowski (editor) Games of No Chance, volume 29 of MSRI Publications, pages 3–12, 1996.
- ^ Brian H. Bowditch. The angel game in the plane (PDF). [2014-06-16]. (原始内容存档 (PDF)于2016-03-04) (英语).
- ^ O. Kloster. A Solution to the Angel Problem (PDF). [2014-06-16]. (原始内容 (PDF)存档于2016-01-07) (英语).
- ^ András Máthé. The Angel of power 2 wins (PDF). [2014-06-16]. (原始内容存档 (PDF)于2016-10-13) (英语).
- ^ Péter Gács. THE ANGEL WINS (PDF). [2014-06-16]. (原始内容存档 (PDF)于2016-03-04) (英语).