Problem #80
Piles of Stones
Laertes and Roxane play another game now as they are tired of drawing in the sand. Instead, they play a game with piles of stones that works as follows:
At the beginning of each turn, the player first chooses one of the piles and then removes some number of stones from it (the whole pile may be removed as well, but at least one stone needs to be removed). The turn then passes to the next player. The player that removes the last stone(s) wins.
Laertes always goes first.
Convince yourself that in a game with three piles of 3, 4, and 5 stones respectively, Laertes will always win if he plays optimally, no matter what Roxane does. Let's say that games with this property have value 1.
Consider 6561 separate games, with four piles, and the number of stones per pile varies between 1 and 9. How many of these games have value 1?