As mentioned in my previous post, here I will give several example of impartial game which turn out to be exactly equivalent to Nim Game.

Nimble
Given a line of squares labeled 0, 1, 2, …. Several coins are placed on some squares (it’s possible to have more than one coin on a single square). Two players take turns. One move consists of taking any one coin and moving it to any square to the left of it. It’s possible that the coin moved into a square already containing coins.

Poker Nim
This game is played as a standard Nim Game, but players have option to either substracting stones (like in standard Nim Game) or adding more stones in a pile but not exceeding the original number of stones in that pile. To ensure the game termination, each player is allowed to add stones at most k (a finite number of) times.

Turning Turtles
Given a horizontal line of N coins with some coins showing heads and some tails. Each turn, a player have to flip one coin from head to tail, and in the same time (if he/she wants), flip one more coin to the left of it.

For example, consider this sequence of N = 10 coins:

1 2 3 4 5 6 7 8 9 10
T H T T H H T T T H

Possible moves from this position are:

Flip one coin from head to tail. Eg., coin in position 6 from head to tail.

Flip one coin from head to tail and flip another coin (from tail to head) to the left of it. Eg., coin in position 6 from head to tail and flip coin in position 3 from tail to head.

Flip one coin from head to tail and flip another coin (from head to tail) to the left of it. Eg., coin in position 6 from head to tail and flip coin in position 2 from head to tail.

Silver Dollar Game (without silver dollar)
This game is played on a line of squares labeled 0, 1, 2, … with several coins are placed in some square such that no two coins are placed in a same square. One move consists of moving one coin to its left onto any empty square and not passing any other coin. The game ends when a player cannot make any legal moves, since all the coins are jammed at the left-end of the strip.

For example, given these 4 coins in position {2, 5, 7, 10}:

Awesome stuff!
In the last example, you can also add a bogus pile with 0 coins initially on the right and then reverse the order of piles {0, 3, 1, 2, 1}. Now this is exactly similar to the first example.

Hi there, just saw your blog and ranking on hackerrank. Would you consider discussing a job with us? It would be a work from home job.

Awesome post! I was trying to solve POJ 1704 Georgia and Bob, and found this article. Learned new stuffs about Game Theory. Thanks.

Thanks , very useful.

Awesome stuff!

In the last example, you can also add a bogus pile with 0 coins initially on the right and then reverse the order of piles {0, 3, 1, 2, 1}. Now this is exactly similar to the first example.

Thanks for the post!