poster248

拿一块

82917
1
从5堆石头中轮流取石头,拿到任意一堆的最后一块石头的玩家赢得游戏,那么谁会赢得游戏?
拿一块
17 人挑战成功
返回挑战
challenge-problem-icon

完成本期挑战需要达到:

大众数学水平

17 / 28 读者挑战成功
题目

在这个尼姆游戏中,有5堆石头,其中两堆每堆有2块石头,还有两堆每堆有3块石头,剩下一堆有4块石头.

fU-PfACPYl-nXsX6H9nUsSjo2tsdNcDod
游戏按照以下规则进行:

两个玩家轮流从堆中拿走石头. 在每一回合中,只能选一堆拿走1块石头.

拿到任意一堆的最后一块石头的玩家赢得游戏. 也就是任何一堆被拿完了,游戏就结束.

假设两个玩家都玩得很好,那么玩家 __________必定能赢得游戏.

选项

1

2

跳过看答案
马EG
橘子数学特约撰稿人
2022年02月15日 12:00

对于大部分游戏来说, 寻找最优解是非常困难的. 以围棋为例, 穷尽所有的计算, 对于全球最快的电脑也几乎是不可能的. 在阿尔法狗出现之前, 电脑只能在小棋盘(如9×9)中变化有限的情况下, 找到最优解.

今天的挑战问题, 与寻找最优解有关. 我们沿着阿尔法狗的步伐, 从一个经典游戏入手, 试图寻找它的最佳解法.

你可以选择先看看这个经典游戏寻找最优解的思路, 也可以跳过阅读直接开始做题.

这个经典游戏叫做“尼姆游戏”, 规则是这样的:

  1. 游戏开始时, 有几堆石头;

  2. 玩家必须轮流选择一堆石头, 并拿走1块或多块石头;

  3. 最后一个拿起石头的人输掉游戏. image

我们先以最简单的情况来探索:两堆石头, 每堆有2块石头. 想一想, 先拿石头的人有必胜法么?

因为每一堆都是2块石头, 无论先从哪边开始都是一样的.

那么, 就有两种情况:1)拿走1块;2)拿走2块.

  • 对于第一种情况, 如图所示:

image 你拿走了1块, 对手可以拿走另外一堆中的2块石头. 那么场上只剩下1块石头, 也就是你刚刚拿走的那堆石头中剩下的. 你不得不最后拿走他, 也就输掉了游戏.

  • 对于第二种情况, 如图所示:

image

你拿走了2块, 对手可以拿走另外一堆中的1块石头. 那么场上还是只剩1块石头. 你又输了.

对于尼姆游戏来说, 有2个堆, 每堆有2个石头组成的开始局, 必胜法是让对方先行. 无论对方策略如何, 你都有应对的方法.

以此类推, 有n个堆, 每堆有个石头组成的开局, 也是有必胜法的.

现在, 你能想出下面这个游戏的必胜法么?

0

发布于3 年前
慕容玖
level4
展开所有评论
发表评论