Nim Game: Problem Statement, Analysis, Solution, and Proof

In the introduction, the author recalls playing a simple take‑away game in middle school, which is formally known as the Nim game—a two‑player, turn‑based mathematical strategy game.

The problem statement asks: given a single heap of stones where each player may remove 1, 2, or 3 stones on their turn, and the player who takes the last stone wins, determine whether the first player can guarantee a win assuming optimal play.

Input: 4 Output: false Explanation: With 4 stones the first player cannot win because any move (removing 1, 2, or 3 stones) leaves a winning position for the opponent.

The analysis observes that positions with fewer than 4 stones are winning for the first player, while exactly 4 stones is a losing position. Extending the observation, any heap size that is a multiple of 4 (8, 12, …) is also losing, because the opponent can always return the game to another multiple of 4 after the first player's move. For heap sizes 5, 6, and 7 the first player can remove 1, 2, or 3 stones respectively to leave 4 stones, forcing a win.

Based on this pattern, the solution is straightforward: the first player wins if and only if the number of stones is not divisible by 4.

func canWinNim(n int) bool { return n % 4 != 0 }

The proof formalizes the reasoning using basic game‑theoretic concepts. If a position N is a multiple of 4, all three possible moves (to N‑1, N‑2, N‑3) lead to positions that are not multiples of 4, which are winning for the next player. Conversely, if N is not a multiple of 4, the current player can remove a number of stones that makes the remaining heap a multiple of 4, leaving the opponent in a losing position. Thus, the losing positions are exactly the multiples of 4, confirming the correctness of the simple modulo‑4 check.