A pub story
The man with the matches
It was one of those evenings when the beer arrived faster than new topics of conversation. At the next table sat an elderly gentleman with a pint in front of him and a box of matches. At some point he pushed the box over to us and asked: "Do you know NIMM?"
None of us did. He laid the matches out on the table in a few rows, some short, some long, "just as they come". The rules fitted into two sentences: whoever's turn it is takes as many matches as they like from one row – one, several or the whole row, but never from two rows at once and never none at all. Then it's the other player's turn. "And whoever leaves the other with exactly one match has won."
It sounded like luck. It wasn't. We lost the first round, then the second, then the fifth. Sometimes he generously let us start, sometimes he started himself, and every time he seemed to know in advance how it would end. One of us cleared whole rows out of sheer defiance, another only ever took a single match. Neither helped.
Over the third pint he at least revealed how he thinks. "I don't count matches," he said, "I count bundles." A row of seven was, for him, a four, a two and a one. A row of five was a four and a one, a row of three a two and a one. There were bigger bundles too: eights, sixteens – always double the one before. "After my move, there is an even number of every bundle size on the table. Then you can do what you like: you mess it up, and I tidy it up again."
We checked on a beer mat. With rows of 1, 3, 5 and 7 there were four ones, two twos and two fours on the table – all even. "That is exactly the kind of position you want to hand over," he said. "Whoever faces it will lose, as long as the opponent makes no mistake."
"And right at the end?" someone asked. He smiled as if he had been waiting for the question. "At the end I do it differently, just once. As soon as my move would leave only rows with a single match each, I leave an odd number of them. Then we take turns, and the last one stays with you."
Then he finished his drink, pocketed the box and left. We kept playing for a long time, using beer mats instead of matches, and eventually we started winning too. Since then we have shown the game to many people. Hardly anyone has found the trick on their own.
By the way, the computer above plays just like the gentleman at the next table: it counts bundles.
Behind the story: Mathematicians call the game Nim. The variant in which whoever has to take the last match loses is known as misère Nim. The mathematician Charles L. Bouton solved it completely in 1901. His "bundles" are the powers of two of the binary system. The layout 1-3-5-7 became famous through the film Last Year at Marienbad (1961) – it is balanced, so whoever starts there loses.