一道+ / edao.plus
#10180

操作与策略·博弈问题

杂题六年级#不变量
题目

甲、乙两人轮流从一堆 20 个石子中取石子，每次只能取 1 个或 2 个，取到最后一个石子的人获胜。

甲先取，甲有没有必胜策略？如果有，应该怎么取？

解法

  1. 分析：3 的倍数（3、6、9、12、15、18...）是必败位置，其他数是必胜位置。

  2. 20 不是 3 的倍数，甲先取 20 − 18 = 2 个，给乙留下 18 个。之后乙取 k 个，甲取 3 − k 个，保持给乙留下 3 的倍数。

    必败位置
    =3, 6, 9, 12, 15, 18...
    初始石子
    =20
    甲第一次取
    =20 − 18 = 2
    给乙留下
    =18（3的倍数）
    初始石子
    20
    甲取2个
    2
    给乙留下
    18

方法

不变量找一个“无论怎么操作都不变”的量，当目标状态里这个量变了，就说明不可能达成。

练一练

甲、乙两人轮流从一堆 25 个石子中取石子，每次只能取 1 个或 2 个，取到最后一个石子的人获胜。甲先取，甲有没有必胜策略？如果有，第一次应该取几个？

相关题目

#10083 圆桌放币·对称策略
不变量
杂题五年级
#10048 等量互换·浓度相等
不变量
应用题六年级