博文
Dec 30th 2012 今日趣题
|||
作为“生命游戏”的发明者和“组合博弈论”的巨擎，他却很反感人们称他为“数学家”。他觉得不务正业的自己只能被称为“数学爱好者”。
Conway的不务正业体现在方方面面，毕业于Cambridge的他，无视了大不列颠为他提供的优雅而清闲的教职，转投Princeton大学，只因Princeton“有着更浓厚的计算学氛围”——这让该校领导被感动的冒鼻涕泡泡，竟破例授予其 “冯诺依曼”终身教职。要知道，这在学界的地位和声望毫不逊于“卢卡斯”教职，后者可是牛逼顿引以为豪常年挂嘴边用以鄙视莱布尼茨的小傲娇啊。
拿到这个职位后，Conway却没做跟计算机学有一毛钱关系的工作。在图论、群论、数论里一通神游之后，Conway迷恋上了发明游戏。在发明了单玩家游戏“困天使”，被数学界拜为天人之后，Conway觉得还不过瘾，发明了零玩家游戏，即大名鼎鼎的“Game of Life”.
Conway的每个数学游戏都有着极其简单和易懂的外壳，任何3岁以上的人都可以毫不费力的理解和操作。但是正由于其构造基础而简约，衍生出的游戏策略往往就蕴含了深刻的数学道理。
今天我们要讲的Conway Game是一个两玩家游戏。玩的时候只需要一根笔和一张纸。
在进行游戏之前，上帝会在纸上随机画几个点，为了简单，我们假设是两个点吧。（这样也方便我去google盗图……忏悔……）
轮到某一个玩家“走棋”时，他要在纸上画一条线连接图中任意两点，或从一个点出发再回到自己，画一个环。然后他要在新得到的线上任意位置给出一个新点。
注意，新的线不允许与包括自身在内的任何线相交，新点也不许与任何旧点重合。且规定，任何一个点不能有超过3个分支。也就是说，当某一个点形成“Y”字型的时候，就可以认为它 “死了”。
游戏的输赢很简单。当轮到你走时，若你没有任何办法画出一条符合规则的线，那么你就输了。
下面就是一个2点游戏的进行过程。
先走的玩家连接了图中两点，并选定了新点，用红色标记。如图（上中）。后手玩家按照规则继续，反复几次之后，到达图（下右）。
此时大部分的点已经被“占用”了3次，不能再参与连线了。而图中两个绿点虽然还“活着”，但由于他们不能自己成环（否则就形成了4个分支），也不能相互连接（无法穿越）。故而到第六张图的时候，先走的一方无法继续，游戏结束，后手胜利。
好吧，我的问题是，
1. Conway 点线游戏，一定会结束么？有没有可能存在一种策略，使得游戏无法结束。毕竟每一次“走棋”，都会导致图上新增一个“活点”。
2. 请计算Conway点线游戏结束的所需的最小步数？若第一问答案是“一定会结束”，请计算游戏结束的最大步数？
3. 由于是Conway游戏属于“完全信息博弈”，所以其实在游戏开始之前，双方就可以判断是否有必胜策略和如何必胜这两个问题了。那么，对于3点的情况和4点的情况，若游戏一定会结束，先走必胜还是后走必胜？这与点在纸上的初始位置关系有关么？
元旦将至，笔者不日将飞往成都，在这里祝大家节日快乐。到那边视网络情况来决定何时发答案吧~~
坚持Geek，首日一问，次日一答，不动摇，嗷呜~~~！！！
此时大部分的点已经被“占用”了3次，不能再参与连线了。而图中两个绿点虽然还“活着”，但由于他们不能自己成环（否则就形成了4个分支），也不能相互连接（无法穿越）。故而到第六张图的时候，先走的一方无法继续，游戏结束，后手胜利。
好吧，我的问题是，
1. Conway 点线游戏，一定会结束么？有没有可能存在一种策略，使得游戏无法结束。毕竟每一次“走棋”，都会导致图上新增一个“活点”。
2. 请计算Conway点线游戏结束的所需的最小步数？若第一问答案是“一定会结束”，请计算游戏结束的最大步数？
3. 由于是Conway游戏属于“完全信息博弈”，所以其实在游戏开始之前，双方就可以判断是否有必胜策略和如何必胜这两个问题了。那么，对于3点的情况和4点的情况，若游戏一定会结束，先走必胜还是后走必胜？这与点在纸上的初始位置关系有关么？
元旦将至，笔者不日将飞往成都，在这里祝大家节日快乐。到那边视网络情况来决定何时发答案吧~~
坚持Geek，首日一问，次日一答，不动摇，嗷呜~~~！！！
PS：
我的果壳网账号 frederyktal，
我的新浪微博： 童年崩坏FML
上面会同时更新我的趣题和解答，欢迎各位的讨论！
https://blog.sciencenet.cn/blog-848464-648188.html
下一篇：Jan 5th 2013 今日趣题 及Dec 30th 趣题讨论
