MIcompany Puzzle: Counting Riddle Matches
The game Nim is played with 2 players and a stack of x matches. In turn, the players can take 1, 2 or 3 matches from the pile. The player who takes the last match wins. Suppose that the players start with a stack of 3 matches, then there are 4 possible game runs (the numbers shown represent the number of matches on the pile):
3 à 0
3 à1 à 0
3 à 2 à 0
3 à 2 à 1 à 0
How many play runs are there when the players start with 6 matches? A move does not have to be tactical, as long as it is legal.
Hint: it is possible to explicitly explain the game progress, but there is a certain pattern in which it can also be faster.
