Game of Nim

"I know a game I always win."
"It's not much of a game if you can't lose."

"Oh, I can lose, but I always win."

—Last Year at Marienbad

James Fixx described this two-player game in his 1972 book Games for the Superintelligent, although it is certainly older.

The game begins with matchsticks arranged in three rows: three on the top, five in the middle and seven at the bottom. Players take turns removing matches, from only one row at a time. The object is to force one's opponent to remove the last match.

The solution involves writing the number of matchsticks in each row in binary and making selections so that there are an even number of each binary digit, except when this would leave only single matches, in which case you want to leave an odd number of single matches.

More general versions of the game exist with different numbers and sizes of rows (or piles, as the case may be), and Reverse Nim is essentially the same game played to lose - and the solution is similar. In all cases, one side has a winning strategy that cannot be beaten if the player follows it carefully. This makes it very easy to implement in a computer game - the human player has the advantage and can win if he does the right thing, but a single slip-up and the computer will win instead.

The Game of Nim makes an appearance in

Film

• Last Year at Marienbad, a surreal French New Wave movie.

Video Games

• There's a very similar minigame in one of the Mario Party games where you have a tree with fruits, coins, and beehives set up in a row, and each of the four players can take one or two items from the tree- if you get the beehive, you're out.
• A variety of this game made an appearance in Super Mario RPG, in which you had to make sure your opponent took the last coin from a box... Although the CPU apparently didn't know how to count, as he would often take multiple coins if there was more than one coin left, causing him to lose.
• The Secret Island of Dr. Quandary had DiscAppear, which is a Nim variant played with compact discs with titles like "The Boston Pops Play the Beach Boys". It's implied that whoever gets stuck with the last disc has to listen to it, but fortunately the player is spared such a fate.
• One EX Mission in Shin Megami Tensei: Strange Journey is to win at a counting-based variant of this game against one of your crewmates, called "Don't Count Thirty". The solution is to control every fourth number - 1, 5, 9, 13, 17, 21, 25, and 29.
• In the Pokémon Black and White Dream World, you can play a similar game against ghost-type Pokemon, where the players take turns blowing out candles. Some candles, however, give you extra points, while others subtract them, and later ones take two turns to extinguish.
• In Teenage Mutant Ninja Turtles: Fall of the Foot Clan for the Nintendo Game Boy, there is a bonus stage where you play a similar game against Krang by removing shurikens until there are none left, with the winner being the one who removes the last shuriken.