A simple nim game:

·        Two players take turn to play the game with a pile of coins.

·        Before the game starts, the players negotiate to determine the settings of the game in terms of

n: the number of coins to begin with,

m: the maximum number of coins a player can take on each turn where m is less than n and is at least 1.

initial turn: which player to start the game, and

the end-game rule: proclaiming the player taking the last coin either as the winner or the loser.

·        Then the players take turn to take away some coins until there is no coin left. Each time the player needs to take at least 1 coin but no more than m coins and also no more than the number of coins still left at that time.

 

Reasoning about the optimal strategy when it is your turn and there are k coins left:

(i)     If k modulus (m+1) equals 0, then it is very bad for you because there is no good move. (Why? Hint: think about groups of m+1 coins.) Just take some number of coins as long as it is allowed by the rule. For example, just taking away 1 coin is fine.

(ii)   If k modulus (m+1) does not equals 0, there is an optimal move at this point for you to win the game. (What is that optimal move? Hint: Essentially you want to make move that ends in a bad situation like (i) for your opponent. )

(i)     If (k-1) modulus (m+1) equals 0, then it is very bad for you because there is no good move. . (Why? Hint: Focus on the first k-1 coins there and the goal is to take the very last one of these n-1 coins to win. ) Just take some number of coins as long as it is allowed by the rule. For example, just taking away 1 coin is fine.

(ii)   If (k-1) modulus (m+1) does not equals 0, there is an optimal move at this point for you to to win the game. (What is that optimal move? Hint: Focus on the first k-1 coins there and the goal is to take the very last one of these n-1 coins to win.)

 

You should play the game against the sample executable for the coach version posted on our website to gain the understanding of the game and figure out the optimal strategy mentioned above. Work on the following cases to ensure you really know how to play the game optimally. Keep making the optimal moves in each of the following cases to see why you (or any person in that role) can always win the game in these cases if you keep making the optimal moves.

(i) n=12 coins in the beginning, at most m=3 coins taken each time by a player, taking the last coin mean winning the game, your opponent starts first.

(ii) n=13 coins in the beginning, at most m=3 coins taken each time by a player, taking the last coin mean winning the game, you start first.

(iii) n=13 coins in the beginning, at most m=3 coins taken each time by a player, taking the last coin mean losing the game, your opponent starts first.

(iv) n=14 coins in the beginning, at most m=3 coins taken each time by a player, taking the last coin mean losing the game, you start first.