天使问题
| 此条目需要扩充。 (2014年6月16日) |
天使问题是由英国数学家约翰·何顿·康威提出的一个博弈论问题[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） （英语）.