perplexus.info :: Games : Real Nim Variations

Real Nim Variations (Posted on 2003-05-18)

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.

Submitted by Charlie

Rating: 4.3333 (3 votes)

Solution: (Hide)

The strategy in this multi-pile (or multi-set) game of nim is to first represent the number in each pile or set in binary. If the sets consist of the suits, then this is four number thirteens. If the sets consist of denominations, then the numbers are thirteen fours.
Then, as you proceed, you take away as many from the one set as is necessary to leave an even number of 1-bits at each bit position. In other words if the binary numbers are written one above the other, leave an even number of 1-bits in each column.
If you are first and are presented with four thirteens, it looks like this:
1101
1101
1101
1101
and you’d be forced to break the parity rather than leave an even number of 1’s in each column. So you don’t want to start this way.
On the other hand, if you are first presented with 13 fours:
100
100
100
100
100
100
100
100
100
100
100
100
100
you can leave your opponent with an even number of 1’s in each column by taking one complete set, say all the kings. There’ll be 12 1’s in the first column and zero in the other two. Your opponent will then be force to break this parity, the dullest way being by taking another complete set, which continues on to an obvious win for you if continued this way to the end. More interesting would be if your opponent took only, say two from one set, say two queens. Then there would be eleven 100’s and one 10. You’d even up the 1-bits by taking as many cards from a different set, say taking two jacks.
In the end, as zero is even, you’d take the last set of cards.
If starting out with 1 card removed from one suit and 2 from another, the numbers come out
1101 (spades)
1101 (diamonds)
1100 (clubs)
1011 (hearts)
All columns can be made to have an even parity by taking one club out, making the binary total for clubs be 1011. At each step, of course the row (suit) to change will be one that has a one bit in the leftmost column requiring change. So in this instance, we could have taken away three of the diamonds, leaving ten, or in binary 1010, which would also leave the opponent with an even parity in each column.

Comments: ( You must be logged in to post comments.)

Subject	Author	Date
more hexanim boards	Dan Porter	2004-01-14 23:42:59
Comment	Dan Porter	2004-01-14 23:10:36
re: Solution?	DJ	2003-05-18 18:13:50
re(3): Solution?	Gamer	2003-05-18 15:48:13
re(2): Solution?	Trevor Leitch	2003-05-18 13:35:49
re: Solution?	Gamer	2003-05-18 11:56:30
Solution?	Trevor Leitch	2003-05-18 07:05:13

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (15)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info