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.

(In reply to re(2): Solution? by Trevor Leitch)

You are right... I misread your solution, not seeing you took 1 whole pile first.

The answer I read somewhere to the answer of this is pretty complicated, but I can't think of one outside Trevor's special case one (for example, what if there were 13, 10, 9, 6)

Divide each into powers of two, then keep them so there is an even number of each power of two. For example, 13, 10, 9, 6 would be:

13=84-1
10=8-2-
09=8--1
06=-42-
_______
---3222

Since there are 3 3s, take 8 from any pile. (For example, take 8 from 13 to leave 5)


If there were 9 6 3 1:

9=8--1
6=-42-
3=--21
1=---1
______
--1123

Split the 8 into 2 4s, then take a (4+1) or 5 from the 9 pile.

Eventually, this will get to a point where there is only 1 card or 1 pile left, then just take that pile.

Posted by Gamer on 2003-05-18 15:48:13