Take away matches

Taking away matches is a zero-sum game for two people.

There are the following variants:

1. Nim games , for example Marienbad
2. One or two: Between two players there is a pile of matches (beans, pebbles, lighters, ...). Both players take turns taking a stick or two sticks. Whoever takes the last wood wins. - Strategy : If you make a whole multiple of 3, you can always make such a multiple and thus win safely.
3. Double or Fibonacci-Nim: There is a pile of matches between two players. One draws alternately. In your turn you take at least one piece of wood (Zugzwang). Whoever starts must leave at least one piece of wood. Then everyone takes at most twice as many sticks as the opponent took on the previous move. Whoever takes the last wood wins. - strategy:

• (a) A path to the goal, represented with recursion :
  • Step 1: If you are allowed to take all the woods, you take all of them and you have won.
  • Step 2: Find the largest Fibonacci number that is not greater than the current number of matches: 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

• Case 1: If both numbers are the same, then there is no move that always wins for this player. Take a stick to give your opponent the opportunity to make a mistake as often as possible. If he answers wrong once, he loses.
• Case 2: Otherwise, form the difference between the two numbers. Just look at this difference as if it were the heap size. You start again with step 1 - and you win for sure.

• (b) All possible ways to the goal:
  If you can take all the woods, you do that. Otherwise you try to produce a sum of Fibonacci numbers ≥3 by removing them, all of them different and no two adjacent, the smallest so large that the opponent cannot take away this number. If that succeeds, you can do it again and again as the game progresses and you are sure to win. If not, the opponent can certainly win with this strategy.
• Example: In the initial situation there are 20 pieces of wood. The next smaller Fibonacci number is 13. The difference is 20-13 = 7. We take 2 woods (because of the goal 5), remainder 18 = 13 + 5. The opponent can remove a wood; then we consider 17-13 = 4 and take one, remainder 16 = 13 + 3. He can remove two, three, or four woods, then we take the rest of the stack of differences and bring the pile to the Fibonacci number 13. (If he takes five or more, we take everything), then we bring it to 8, 5, 3 and eventually win.

Individual evidence

1. ↑ Inventor: Robert E. Gaskell - according to Martin Gardner, Mathematischer Zirkus, Ullstein [without location] 1988, ISBN 3550076924 , page 177