来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/nim-game
你和你的朋友,两个人一起玩 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,根据流程 33 我们知道此时先手必败;
…
到这里,我们猜想 当起始局面石子数量为 4 的倍数,则先手必败,否则先手必胜(即 n % 4 != 0 时,先手必胜)。
然后我们通过「归纳法」证明一下该猜想的正确性。
在上面的「找规律」分析中,我们分情况讨论了最后一个决胜回合(我们称「剩余石子数量少于等于 4 的局面」为最后回合)的情况:如果交由先手的石子数量为 4,那么先手必败,否则先手必胜。
而对于「最后回合」前的任意回合(石子数量大于 4),我们需要证明 先手可以通过调整所选石子数量,来维持「n % 4 != 0」直到最后回合。
如果起始对先手而言满足「n % 4 != 0」,此时先手可以通过选择石子数量为「n % 4」来确保交到后手的局面为 4 的倍数。
那么根据推论,此时的原始后手作为下一回合的先手角色,且面临石子数量为 4 的倍数的局面,为必败态。
进一步的解释就是,由于原始后手面临石子数量为 4 的倍数的局面,且只能选 1 - 3 个石子,因此无论如何选择,重新回到原始先手的仍然满足「n % 4 != 0」(非 44 的倍数)。
因此 原始先手只需要确保每次都选择「x % 4」个石子(x 为当前石子数量),就可以确保交由自己的局面一直满足「x % 4 != 0」,交由对方的局面一直满足「x % 4 == 0」,直到最后回合的到来。
至此,我们证明了 如果起始石子数量 n 满足「n % 4 != 0」条件,那么先手必胜。
class Solution: def canWinNim(self, n: int) -> bool: return n % 4 != 0