囚犯拿豆子

描述：有一群囚犯需要从一个装满豆子的罐子中拿豆子。每个人每次至少拿 1 颗，最多拿 4 颗。拿到最后一颗豆子的人将被释放。
请问，先手是否有必胜策略？如果有，策略是什么？

问题分析

1. 游戏规则：

   • 玩家轮流拿豆子。
   • 每次必须拿 1 ~ 4 颗。
   • 最后一个拿走豆子的人获胜（被释放）。

2. 核心目标：

   • 先手是否有必胜策略？
   • 关键位置在哪里？

3. 数学建模：

   • 设当前罐子里有 N 颗豆子，如果你能让对手面对一个必输的局面，那么你就能确保胜利。
   • 反之，如果你面对的是一个必胜的局面，那么你就只能听天由命。

找规律

我们假设：

• 如果轮到你时，剩余豆子的数量让你无论怎么拿，都会让对手处于必胜状态，那么这是一个必输局面。
• 如果轮到你时，你能选择一个数量，使对手进入必输状态，那么这是一个必胜局面。

基础案例

• 1 颗豆子：先手直接拿走，获胜（先手胜）。
• 2 颗豆子：先手拿 1 颗，留 1 颗给对手，对手必胜（先手败）。
• 3 颗豆子：先手拿 2 颗，留 1 颗给对手，对手必胜（先手败）。
• 4 颗豆子：先手拿 3 颗，留 1 颗给对手，对手必胜（先手败）。
• 5 颗豆子：先手可以拿 4 颗，留 1 颗给对手，让对手必败（先手胜）。
• 6 颗豆子：无论先手怎么拿，都会让对手有必胜方案（先手败）。
• 7 颗豆子：先手可以拿 1 颗，留 6 颗给对手，让对手面对必败局面（先手胜）。
• 8 颗豆子：先手可以拿 2 颗，留 6 颗给对手（先手胜）。
• 9 颗豆子：先手可以拿 3 颗，留 6 颗给对手（先手胜）。
• 10 颗豆子：先手可以拿 4 颗，留 6 颗给对手（先手胜）。
• 11 颗豆子：无论先手怎么拿，都会让对手有必胜方案（先手败）。

发现规律

• 关键点：如果 N 是 5 的倍数，先手必败，否则先手必胜！
• 证明：
  • 先手面对 5、10、15、20... 这样的局面时，无论拿多少颗（1 ~ 4），都会把局面变成 N-1、N-2、N-3 或 N-4，而其中至少有一个必胜局面（即不是 5 的倍数）。
  • 但如果 N 不是 5 的倍数，那么先手可以拿掉一定数量的豆子，使得剩下的豆子变成 5 的倍数，让对手进入必败状态。

必胜策略

1. 如果豆子总数 N 是 5 的倍数，先手无论如何都会输。
2. 如果 N 不是 5 的倍数，先手应该拿走 1 ~ 4 颗，使得剩下的豆子变成 5 的倍数。

举例验证

N（豆子数）	先手策略	结果
5	无解（无论如何都会输）	败
6	拿 1 颗，剩 5 颗（对手败）	胜
7	拿 2 颗，剩 5 颗（对手败）	胜
8	拿 3 颗，剩 5 颗（对手败）	胜
9	拿 4 颗，剩 5 颗（对手败）	胜
10	无解（无论如何都会输）	败
11	拿 1 颗，剩 10 颗（对手败）	胜

总结

• 核心规律：5 的倍数是必败局面，否则先手有必胜策略。
• 必胜策略：如果 N 不是 5 的倍数，先手应该让剩下的豆子变成 5 的倍数，这样对手无论如何都会输。
• 这道题本质上是尼姆博弈（Nim Game）的一种特殊形式，通过找出必败状态，反向推导必胜策略。