英文原文
You are playing the following Nim Game with your friend:
- Initially, there is a heap of stones on the table.
- You and your friend will alternate taking turns, and you go first.
- On each turn, the person whose turn it is will remove 1 to 3 stones from the heap.
- The one who removes the last stone is the winner.
Given n, the number of stones in the heap, return true if you can win the game assuming both you and your friend play optimally, otherwise return false.
Example 1:
Input: n = 4 Output: false Explanation: These are the possible outcomes: 1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins. 2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins. 3. You remove 3 stones. Your friend removes the last stone. Your friend wins. In all outcomes, your friend wins.
Example 2:
Input: n = 1 Output: true
Example 3:
Input: n = 2 Output: true
Constraints:
1 <= n <= 231 - 1
中文题目
你和你的朋友，两个人一起玩 Nim 游戏：
- 桌子上有一堆石头。
- 你们轮流进行自己的回合，你作为先手。
- 每一回合，轮到的人拿掉 1 - 3 块石头。
- 拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。
示例 1：
输入：n = 4
输出：false
解释：如果堆中有 4 块石头，那么你永远不会赢得比赛；
因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。
示例 2：
输入：n = 1 输出：true
示例 3：
输入：n = 2 输出：true
提示：
1 <= n <= 231 - 1
通过代码
高赞题解
博弈论
这是一道 Nim 游戏的简化版。
在不知晓博弈论结论前，可以先通过找规律得到猜想，然后再从「何种情况下，先手会处于必胜态」的角度来进行分析。
根据题意，我们尝试从小范围数据的情况进行讨论：
- 如果落到先手的局面为「石子数量为 $1$ - $3$」的话，那么先手必胜；
- 如果落到先手的局面为「石子数量为 $4$」的话，那么先手决策完（无论何种决策），交到后手的局面为「石子数量为 $1$ - $3$」，即此时后手必胜，对应先手必败（到这里我们有一个推论：如果交给先手的局面为 $4$ 的话，那么先手必败）；
- 如果落到先手的局面为「石子数量为 $5$ - $7$」的话，那么先手可以通过控制选择石子的数量，来使得后手处于「石子数量为 $4$」的局面（此时后手必败），因此先手必胜；
- 如果落到先手的局面为「石子数量为 $8$」的话，由于每次只能选 $1$ - $3$ 个石子，因此交由后手的局面为 $5$ - $7$，根据流程 $3$ 我们知道此时先手必败；
…
到这里，我们猜想 当起始局面石子数量为 $4$ 的倍数，则先手必败，否则先手必胜（即 n % 4 != 0 时，先手必胜）。
然后我们通过「归纳法」证明一下该猜想的正确性。
在上面的「找规律」分析中，我们分情况讨论了最后一个决胜回合（我们称「剩余石子数量少于等于 $4$ 的局面」为最后回合）的情况：如果交由先手的石子数量为 $4$，那么先手必败，否则先手必胜。
而对于「最后回合」前的任意回合（石子数量大于 $4$），我们需要证明 先手可以通过调整所选石子数量，来维持「n % 4 != 0」直到最后回合。
如果起始对先手而言满足「n % 4 != 0」，此时先手可以通过选择石子数量为「n % 4」来确保交到后手的局面为 $4$ 的倍数。
那么根据推论，此时的原始后手作为下一回合的先手角色，且面临石子数量为 $4$ 的倍数的局面，为必败态。
进一步的解释就是，由于原始后手面临石子数量为 $4$ 的倍数的局面，且只能选 $1$ - $3$ 个石子，因此无论如何选择，重新回到原始先手的仍然满足「n % 4 != 0」（非 $4$ 的倍数）。
因此 原始先手只需要确保每次都选择「x % 4」个石子（$x$ 为当前石子数量），就可以确保交由自己的局面一直满足「x % 4 != 0」，交由对方的局面一直满足「x % 4 == 0」，直到最后回合的到来。
至此，我们证明了 如果起始石子数量 $n$ 满足「n % 4 != 0」条件，那么先手必胜。
代码：
[]class Solution { public boolean canWinNim(int n) { return n % 4 != 0; } }
- 时间复杂度：$O(1)$
- 空间复杂度：$O(1)$
其他「博弈论」相关内容
意犹未尽？可以看看如下博弈论题目。
| 题目 | 题解 | 难度 | 推荐指数 |
|---|---|---|---|
| 810. 黑板异或游戏 | LeetCode 题解链接 | 困难 | 🤩🤩🤩🤩 |
| 877. 石子游戏 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。
最后
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/
也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 118515 | 167405 | 70.8% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
相似题目
| 题目 | 难度 |
|---|---|
| 翻转游戏 II | 中等 |
