一道 / edao.plus

#10180

操作与策略·博弈问题

六年级·杂题·操作与策略·博弈

题目

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

解法

分析：3 的倍数（3、6、9、12、15、18...）是必败位置，其他数是必胜位置。
必败位置 = 3, 6, 9, 12, 15, 18...
初始石子 = 20
甲第一次取 = 20 − 18 = 2
给乙留下 = 18（3的倍数）
倒推法分析必胜策略
20 不是 3 的倍数，甲先取 20 − 18 = 2 个，给乙留下 18 个。之后乙取 k 个，甲取 3 − k 个，保持给乙留下 3 的倍数。
初始石子
20
甲取2个
2
给乙留下
18
甲的必胜策略

练一练

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

相关题目

#10067 装信错排·欧拉问题

递推法 / 容斥原理 / 枚举法

杂题六年级

#10073 双工序加工·最短总工时

杂题六年级