Select how many to remove:
Move History
What is Bachet's Game?
Bachet's Game (also known as the Subtraction Game) is a two-player mathematical game of perfect information. There is a pile of N items, and two players alternate taking between 1 and M items. The player who takes the last item wins.
The (M+1) Rule
The key insight: The first player has a winning strategy if and only if N is NOT a multiple of (M+1). If N mod (M+1) = 0, the second player can always win with optimal play.
N mod (M+1) ≠ 0 → First player wins
N mod (M+1) = 0 → Second player wins
Winning Strategy
If it's your turn and the remaining items N is not a multiple of (M+1), take exactly N mod (M+1) items. This leaves your opponent with a multiple of (M+1), which is a losing position. Whatever they take (k items), you take (M+1-k) items on your next turn, maintaining the multiple.
Connection to Modular Arithmetic
Bachet's Game is fundamentally about modular arithmetic. The "safe" positions are exactly those where the count is 0 mod (M+1). Each pair of moves (one by each player) can total at most M+1, so if you leave your opponent at 0 mod (M+1), they cannot escape.
Connection to Nim
Bachet's Game is a special case of the mathematical game Nim. In Nim, there are multiple piles and a player can take any number from one pile. The Sprague-Grundy theorem provides a complete solution for all impartial games, including Bachet's Game. The Grundy value of a position with n items is n mod (M+1).
Applications
- Combinatorial game theory fundamentals
- Algorithm design and dynamic programming
- Number theory and modular arithmetic
- Strategic thinking in competitive scenarios
- Teaching mathematical reasoning and proof
Misere Convention
In the misere version, the player who takes the LAST item LOSES. The strategy changes significantly: if N mod (M+1) = 1, you are in a losing position; otherwise, take items to leave a count of 1 mod (M+1).
Variable Maximum
Instead of a fixed M, the maximum removal could increase each turn (e.g., doubling). These variants create richer mathematical structures and may not have simple closed-form solutions.
Subtraction Set Games
Generalize beyond 1 to M: allow removal from a specific set S of numbers (e.g., S = {1, 3, 4}). The analysis uses the Sprague-Grundy theorem, computing Grundy values for each position.
Multi-Pile Versions
With multiple piles, the game becomes equivalent to Nim. The winning strategy uses binary XOR (nim-sum) of pile sizes. If the nim-sum is non-zero, the first player wins.
Fibonacci Nim
A beautiful variant where the maximum you can remove is twice what your opponent just took. Zeckendorf's theorem provides the winning strategy using Fibonacci number representations.
Claude Gaspard Bachet de Méziriac (1581-1638)
Bachet was a French mathematician, linguist, and poet. He is best known for his 1612 book "Problèmes plaisants et délectables qui se font par les nombres" (Pleasant and Delectable Problems with Numbers), one of the earliest books on recreational mathematics.
Contributions to Mathematics
- Wrote one of the first recreational mathematics books (1612)
- Studied Fibonacci-like sequences and their properties
- Translated Diophantus's "Arithmetica" into Latin (1621)
- His translation inspired Fermat to write Fermat's Last Theorem in the margin
- Studied magic squares and number puzzles
Game Theory History
While Bachet described the game in 1612, the formal mathematical analysis came much later. John von Neumann and Oskar Morgenstern established game theory as a mathematical discipline in 1944. The Sprague-Grundy theorem (1935-1939) provided tools for analyzing impartial combinatorial games like Bachet's Game.
Chinese Origin
In Chinese mathematical tradition, this game is known as "Ba Shang Bo Yi" (Bachet's Game). It has been used extensively in mathematics education in China to teach strategic thinking and modular arithmetic. The name "Ba Shang" is a transliteration of "Bachet."