Nim, the classic combinatorial game where two players take turns choosing stones from piles, can be played with many variations. In the regular version, two players take turns removing any number of stones from a single pile in the game and the last player able to make a move wins. Greedy Nim is a variation where the players are restricted to choosing stones from only the largest pile(s).
Contents |
There are two types of Greedy Nim games: one where there is an odd number of largest piles and one where there is an even number. Let the case with an even number of largest piles be called X and the case with an odd number of largest piles be called Y.
Every option of a position in X is in Y. (The moving player must take from the/a largest pile, reducing the number of largest piles by one – thus leaving an odd number of largest heaps)
Every position in Y has at least one option in X. (If there is only one largest heap and an odd number of second largest heaps, the moving player should take enough stones so that the heap becomes the same size as the second largest heap(s). Otherwise, the moving player can simply take all of a largest heap)
Theorem 2.13 in Lessons in Play
Suppose the positions of a finite impartial game can be partitioned into mutually exclusive sets A and B with the properties:
Every option of a position in A is in B; and
Every position in B has at least one option in A.
Then A is the set of P-positions and B is the set of N-positions.
Since Greedy Nim is a finite, impartial game and X and Y are mutually exclusive sets, X is the set of P-positions (previous player wins) and Y is the set of N-positions (next player wins). Thus, with optimal game strategy, the next player to move on a game with an odd number of largest heaps will win and the next player to move on a game with an even number of largest heaps will lose.
Greedy Nim Misère has the same rules as Greedy Nim, but here the last player able to make a move loses.
The following is a list of some possible games and their positions (P = previous player win and N = Next player win with optimal game play)
where (n, m, r,s є N; n > 1; m > n; r > m; s > r)
1 heap:
1 − P
n - N (reduce to 1)
2 heaps:
1,1 - N (reduce to 1)
1,n - N (reduce to 1)
n,n - P
n,m - N (reduce to n,n)
3 heaps:
1,1,1 - P
1,1,n - N (reduce to 1,1,1)
1,n,n - P
1,n,m - N (reduce to 1,n,n)
n,n,n - N (reduce to 1,n,n)
n,n,m - N (reduce to 1,n,n)
n,m,m - P
n,m,r - N (reduce to n,m,m)
4 heaps:
1,1,1,1 - N (reduce to 1,1,1)
1,1,1,n - N (reduce to 1,1,1)
1,1,n,n - P
1,1,n,m - N (reduce to 1,1,n,n)
1,n,m,m - P
1,n,m,r - N (reduce to 1,n,m,m)
n,n,n,n - P
n,n,n,m - N (reduce to n,n,n,n)
n,n,m,m - P
n,n,m,r - N (reduce to n,n,m,m)
n,m,m,m - N (reduce to n,n,m,m)
n,m,m,r - N (reduce to n,n,m,m)
n,m,r,r - P
n,m,r,s - N (reduce to n,m,r,r)
It can be observed that (with the exception of each heap only having one stone) an odd number of largest heaps will be an N game and an even number of largest piles will be a P game, just like in regular Greedy Nim. In the case that each heap only has one stone, the opposite is true – an even number of heaps is an N game and an odd number is a P game. Thus, whether you are playing Greedy Nim or its Misère version, optimal game play is the same until you get down to each heap having only one stone.
Elwyn R. Berlekamp, John Horton Conway, Richard K. Guy: Winning Ways for Your Mathematical Plays
Michael H. Albert, Richard J. Nowakowski, David Wolfe: Lessons in Play: An Introduction to Combinatorial Game Theory