Communications of the ACM

Last byte

Card Nim

By Dennis Shasha
Communications of the ACM, October 2022, Vol. 65 No. 10, Page 96
10.1145/3555723
Comments

In a game called Card Nim, each player has a collection of cards, each with a number on it. In each turn a player reveals a card and removes a number of stones equal to the number on the card. To win on a move, a player must play a card whose number is equal to the number of stones remaining. To lose on a move, a player plays a card whose number is greater than the number of stones remaining.

Warm-Up: Suppose there are five stones left and each of the two players Bob and Alice has three cards with 1, 2, and 3, respectively. Alice goes first. Who wins?

Solution: Bob wins. If Alice removes 2 or 3, then Bob can win immediately with 3 or 2 respectively. So, Alice removes 1. Now Bob removes 3, leaving 1. Now A has only cards with numbers greater than 1 so she loses.

Question: There are 10 stones left and each player has cards with 1, 2, 3, 4, 5. Alice goes first. Who wins?

Solution: Alice wins this time.

Alice removes 4. If Bob removes 1, 3, 4, or 5, then that leaves 5, 3, 2, or 1 and Alice has cards for those, so will win. If Bob removes 2, then there are 4 left, so Alice removes 2 leaving 2. Bob then removes 1 to stay in the game (all of B's other cards are 3 or greater) and Alice wins by removing 1.

Question: There are 10 stones left, but now each player has cards of only 1, 2, 3, and 4. Who can force a win?

Solution: Bob wins. If Alice removes 4. then Bob removes 1, leaving 5. Then Alice removes 1, 2, or 3 and Bob wins by removing 4, 3, or 2 respectively.

Alice removes 3. Bob removes 4, leaving 3. Alice can now only remove 1 or 2 and then Bob will take 2 or 1 respectively.

Figure. Alice goes first. A move consists of laying down a card with some number N and taking that many stones. If N is greater than the number of stones, then the mover loses. If N = the number of stones, then the mover wins. Who wins the game?

Alice removes 2. Bob removes 3. Alice can now remove 1, 3, or 4. Bob wins with 4, 2, or 1 respectively.

Alice removes 1. Bob removes 4. Alice can now remove 2, 3, or 4 and Bob wins with 3, 2, or 1 respectively. End of solution.

Question: In three-person Card Nim, each player has cards and they play in turn. Consider a setting in which Bob, Alice, and Carol each has cards 1, 2, 3, 4, 5. There are 10 stones. Can Alice and Carol always guarantee that Bob will not win, no matter what the order of play? (Player p wins in a multiplayer game means either that all other players lose or that p gets the last stone.)

Solution: Suppose Bob goes first and choose to remove b1 stones. If b1 is 5, then the next player removes 5, so Bob does not win. Even if b1 < 5, the next two players can arrange to remove the rest of the stones.

If Bob goes second, then suppose Alice starts by removing 4. Regardless of the card Bob chooses, he cannot win in that move. However, he must leave five or fewer stones so Carol will win.

If Bob goes third, then Alice and Carol can each remove five. End of solution.

Note: The two-person game can be solved by dynamic programming. For example, suppose Alice has certain cards with integer values (which can repeat) a1, a2, … ak. Bob has certain cards with integer values (again, there can be repeats) b1, …, bj. There are N stones to start with. Alice goes first.

Upstart: In the three-person game, for which values of s and k does the following hold: given s stones initially, is there some value of k ≤ s/3 such that each of Alice, Bob and Carol has cards 1 through k, Bob goes last and Bob can be sure to win? Example: s = 3. k = 1. Alice and Carol each remove 1 and Bob wins.

Back to Top

Back to Top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2022 ACM, Inc.

---

No entries found