Nim: The Game You Can Always Win and 15-puzzle
#Demonstration by Rohan Awasthi (presenter) and Mayank Yadav
Introduction
#Nim: The Game You Can Always Win
#Two players sit across a table with a pile of craft sticks. On each turn, a player picks up one or more sticks. The player forced to take the very last stick loses — or, in another version, the player who takes the last stick wins. The rules are simple enough to explain in thirty seconds, yet hidden inside this game is a complete mathematical theory that lets one player win every single time, no matter what the other does.
In this demonstration, two players take turns removing sticks from one or more piles on the table. One player has secretly learned the winning strategy — and no matter how cleverly the other tries to outmanoeuvre them, the outcome is always the same. After a few rounds, the strategy is revealed: the answer lies not in intuition or luck, but in binary arithmetic. Nim is one of the oldest and most elegant illustrations of how pure mathematics can give a complete, provable solution to a seemingly open-ended game.
15-puzzle
#The "15 puzzle" is a sliding square puzzle commonly (but incorrectly) attributed to Sam Loyd. However, research by Slocum and Sonneveld (2006) has revealed that Sam Loyd did not invent the 15 puzzle and had nothing to do with promoting or popularizing it. The puzzle craze that was created by the 15 puzzle began in January 1880 in the United States and in April in Europe and ended by July 1880. Loyd first claimed in 1891 that he invented the puzzle, and he continued until his death a 20 year campaign to falsely take credit for the puzzle. The actual inventor was Noyes Chapman, the Postmaster of Canastota, New York, and he applied for a patent in March 1880.
The 15 puzzle consists of 15 squares numbered from 1 to 15 that are placed in a 4×4 box leaving one position out of the 16 empty. The goal is to reposition the squares from a given arbitrary starting arrangement by sliding them one at a time into the configuration shown above. For some initial arrangements, this rearrangement is possible, but for others, it is not.
Precautions
#No physical hazards — this is a table-top game using craft sticks. Keep the piles clearly separated so players can count accurately at a glance. Agree on the winning condition (last stick wins, or last stick loses) before each round begins.
Materials Required
#- A collection of craft sticks (ice-lolly sticks) or matchsticks
- A flat table surface where sticks can be arranged in clear piles
Science Behind It
#Nim: The Game You Can Always Win
#Nim belongs to the mathematical field of combinatorial game theory: the study of two-player games with perfect information and no randomness, where both players know everything about the position. The key result, proved by Charles Bouton in 1901, is that a position in Nim is a losing position for the player whose turn it is if and only if the nim-sum of all the pile sizes is zero.
The nim-sum is computed by writing each pile size in binary and then adding column-by-column without carrying — this is the bitwise XOR operation. For example, three piles of 3, 5 and 6 sticks have binary representations 011, 101 and 110. Their XOR is 000, so the pile sizes XOR to zero — meaning whoever just moved has left a losing position for their opponent. Any pile configuration with a non-zero nim-sum is a winning position: there always exists a move that brings the nim-sum to zero, and from a zero position every possible move creates a non-zero nim-sum for the other player to face.
The winning strategy is therefore: after each of your opponent's moves, compute the nim-sum of all piles. If it is non-zero, there exists a move that makes it zero — find and make it. If your opponent plays perfectly from a zero-sum position, no such move exists, and you are in trouble; but once a non-zero position is reached, perfect play guarantees the win. The elegance of Nim is that what looks like guesswork is actually completely solved mathematics — a lesson in how abstract algebra (here, arithmetic in GF(2)) underpins a real-world game.