The puzzle
“A Game of Nim” asked for the strategy in a game in which two persons take turns removing cards from a deck, limited to 1, 2 or 3 cards.
However, there is a more interesting version of Nim, in which players can take as many as they want, but from only one pile or set of objects in a turn, where there are several piles or sets present.
If done with cards, one way of setting the rule could be that in one turn you might take as many as you want from any one suit. Another choice for the rule might be to take as many as you want of a given denomination. The object is again to be the person to take the last card.
If you were to play first (take the first set of cards), which of the two rules of the preceding paragraph would you want to use and why? (i.e., would you rather it limit one player’s turn to one suit or to one denomination?)
Finally, if the rules were that each play the player can take as many as desired of any one suit, but play were to start with the king of clubs removed, as well as the king and queen of hearts, what would be the strategy to win then? This is the equivalent of having a different number of objects in two of the four piles: 13, 13, 12 and 11.
This is very intuitive and not mathematical in the slightest, so please bear with me...
I can't prove it, but I think the answer is that as first player you would want to limit each turn to removing cards within a denomination, and would lose if playing the game within suits instead.
The basic reasoning I have is that after a player's turn, he will win if the cards left on the table form some sort of "symmetrical pairing"... for instance, if there are two groups of three cards left, or two groups with one card and six groups with two each, etc. If this is the case, there must be an even number of piles left, and no matter what the other player does, one can use their own turn to restore this balance. Thus, as first player, if there are thirteen piles (as there would be with denominations), just remove one pile - the resulting spread (12 piles of four cards each) is symmetric, and the first player can mirror the second player's move until player 1 wins. However, if there are only four piles at the start (as there would be with suits), the spread is already symmetric, and the second player can mirror the first player until player 2 wins.
Regarding the third possibility with some cards missing, I would say the first player should remove a card from the pile with 12 (i.e. remove one club), leaving a symmetric spread of 13, 13, 11, 11... this is again a winning situation.
Solution?
