040 · Nim Game

algorithm

Published

June 18, 2026

Problem

你正在和朋友玩一个取石子游戏。

桌子上有 n 块石头。你们两个人轮流取石头，并且你先手。

每一回合，当前玩家可以取走：

谁取走最后一块石头，谁就获胜。

给定整数 n，请判断：在你和对手都采用最优策略的情况下，你是否一定能赢。

例如：

n = 4

如果你先取 1 块，对手可以取走剩下的 3 块。

如果你先取 2 块，对手可以取走剩下的 2 块。

如果你先取 3 块，对手可以取走剩下的 1 块。

无论你第一步怎么取，对手都能取走最后一块石头，所以答案是：

false

再比如：

n = 5

你可以先取走 1 块石头，留给对手 4 块。之后不管对手取多少，你都有机会取走最后一块石头，所以答案是：

true

示例 1

Input:  n = 4
Output: false

解释：你第一步只能取 1、2 或 3 块石头，对手都可以在下一步取走最后的石头。

示例 2

Input:  n = 1
Output: true

解释：你可以直接取走唯一一块石头，所以你获胜。

示例 3

Input:  n = 5
Output: true

解释：你可以先取走 1 块石头，让对手面对剩下的 4 块石头。