# Game of Nim for the Classroom — Don't Take the Last Coin Source: https://decka.dev/classroom/game-theory/game-of-nim Pairs play the twenty-one game on their phones: take one, two or three coins, and whoever takes the last coin loses. The big screen counts who won by seat, lays every turn on a strip by the coins left, and the traps sink before the pen works back from the last coin. Then one more coin turns the winning seat around. ## What it teaches Students find the twenty-one game's winning strategy in their own games: the piles of 1, 5, 9, 13, 17 and 21 coins sink on the strip, because whoever has one on their move loses to a player who never misses. They derive those traps by backward induction from the last coin, and act two, from twenty-two coins, shows them that the winning rule is about positions, not seats. ## The game of Nim, and how the twenty-one game is won Nim is a family of games in which two players take turns removing objects from piles. The twenty-one game is its simplest member: one pile of twenty-one coins, and each turn takes one, two or three of them. In this lesson whoever takes the last coin loses. Every student plays one partner through their phones, quick game after quick game, and the first move passes between them from one game to the next. The big screen never shows a game in progress: each finished game drops as a chip into one of two trays, won by the player who moved first or won by the player who moved second. Take the sample room the lesson is built and tested on: thirty simulated students in fifteen pairs. In act one they finished 46 games, and 3 more were still going at the bell, so they are not counted. The player who moved first won 18 of the 46, and the player who moved second won 28. Then the trays step back and the strip takes the board: all 508 turns from those games, one column for each number of coins the mover faced, from 21 on the left down to 1. Above the line are the turns whose mover went on to win, and below it the turns whose mover went on to lose. Some columns sink. Every turn taken with 5 coins left was in a game its mover went on to lose, 0 won and 46 lost, and so was every turn taken with 1 coin left, 0 and 46. Column 9 reads 0 won and 37 lost, 13 reads 4 and 29, 17 reads 7 and 19, and the starting column, 21, reads 18 and 28: the trays' own count, because every game starts there with the first mover to move. The columns sink deepest near the end of the game, where a beginner has the fewest chances to escape. These six piles are the traps. The pen finds them by working backward from the last coin, one rung for each press of Next. That is backward induction. With 1 coin left you must take it, and you lose. With 2, 3 or 4 you can leave your partner that 1 coin, so those piles win. With 5, every take leaves 2, 3 or 4 and hands your partner the win, so 5 is a trap. With 6, 7 or 8 you can leave 5, so 9 is the next trap, and so on up: 13, 17 and 21. Every trap is four more than the last, because whatever your partner takes, one, two or three, you can take the rest of four. So from twenty-one, whoever moves first loses, if the other player never misses a trap. Before act two, everyone says whether they would rather move first or second. In the sample room 29 of the 30 answered: 8 chose first and 21 chose second. Act two starts the pile at twenty-two, one coin more, with the same partners, and its 41 finished games went the other way: the player who moved first won 31 and the player who moved second won 10. The traps stayed where they were: on act two's strip, 17 reads 0 won and 40 lost, and 13, 9, 5 and 1 each read 0 won and 41 lost. From twenty-two, move first and take one, leaving twenty-one. So the twist separates two rules a room may have learned in act one: a seat rule, "go second", which only held from twenty-one, and a position rule, "leave your partner a trap", which wins from either seat. The games stay private. The big screen shows counts only, never a game in progress, a move or a pair, and each phone shows its own games and, once the pen is dry, its own turns. With an odd number of students, the one without a partner plays the house player: a labelled computer partner that plays the perfect move by the same rule the pen draws, and whose games are never counted on the screen. A note for the teacher: let the room find the traps before the pen does. When the strip lands, ask which coins' stacks sank before you press Next. The four rungs are one Next each, and your view shows the question to put to the room before each one, such as "If 5 is a trap, where is the next one?" If a room of beginners leaves the traps shallow, the pen still rings them where the rule puts them, and the gap is a question for the debrief: why did the room's games and the rule disagree there? Try the screen-and-phone preview with fictional classmates, who play through the same runtime as the lesson: you run the projector's steps and play one student's phone. The classmates are illustrative, not observations of a real class. To play the game on your own, play the computer above. ## Classroom debrief Which seat won more in the first act? Did that still hold with twenty-two coins? Why not? When you had five coins on your move, what happened? Why couldn't you escape? If five is a trap, what is the next trap up, and how did the pen find twenty-one? You may choose the pile size, and your partner chooses who goes first. Which sizes do you pick? Where else do people decide by working back from the end: a chess endgame, a deadline, a negotiation? ## Game of Nim questions, answered ### What is the game of Nim? Nim is a family of two-player games in which players take turns removing objects from piles, and whoever takes the last one wins or, in the version this lesson plays, loses. The twenty-one game is its simplest form: one pile of twenty-one coins, one to three coins a turn. Nothing is hidden and nothing is left to chance, so from every pile one of the two players can force a win, and the lesson lets the room find out which. ### What is the winning strategy for the twenty-one game? Leave your partner a trap: 1, 5, 9, 13, 17 or 21 coins, one more than a multiple of four. From any other pile one take does it, so take enough to bring the pile down to the next trap. After that, answer a take of one with three, two with two and three with one, so every pair of turns removes four coins and your partner meets every trap down to the last coin. From twenty-one the first mover already faces a trap, so the second player wins with perfect play. ### Why does act two start at twenty-two? One more coin changes the winning seat and leaves the traps where they were. From twenty-two the first mover takes one and leaves twenty-one, so moving first now wins. A room that learned "go second" in act one loses with it, and a room that learned "leave a trap" wins from either seat. Asking which seat they would rather take before act two shows the room which of the two it learned. ### How are pairs made, and what if the class has an odd number? Students are paired when act one starts and keep the same partner for both acts. They play through their phones, so they need not sit together. The student without a partner plays the house player: a computer partner, labelled on every screen, that plays the perfect move by the same rule the pen draws, and takes one coin when it has no winning move. Its games are never counted on the big screen. Anyone who joins after the pairs are made plays the house player too, and a student whose partner stops moving for a minute can switch to it. ### Does anyone see who won or lost? Not by name. The big screen shows counts only: finished games in each tray and turns on the strip, never a game in progress, a move, a pair or a name. Each phone shows only its own games, and its own turns once the pen has inked the traps. ### Can I play the game on my own? Yes. Play the computer on this page: it plays by the same rule as the lesson's house player, and a strip under the board counts the piles you had on your move in the games you lost. You move first in the first game, and the first move changes hands after every game, as it does in the lesson. ### Can I change the number of coins? Not in this version. The lesson starts at twenty-one and then twenty-two, because its twist needs act one to start on a trap and act two one coin above it. You can change every clock, and the words on the screen and the phones, before you run it. ### How long does it take? Plan fifteen to twenty minutes: five minutes of play from twenty-one and four from twenty-two, each on its own clock, a forty-five-second prediction between them, and the strip, its four rungs and the debrief at your pace. Every clock is a setting you can change before you run it. ## Run the lesson Present the boards in PowerPoint and Decka. Students scan a QR code or open the session link to join from their phone browsers.