An Interview Experience

8 April, 2011

I don't like to present in interview panels unless really required. Today I had to be in an interview panel. Good puzzle I recapped after long time.

Two players A and B playing a game (similar to game of Nim). Given a pile of N coins, the players need to pick coins from the pile. In each move a player can pick atleast 1 and utmost m coins. The player who makes the last move is the winner.

For example if A starts the game, he can pick 1, 2, 3, ... m coins from the pile. Then B can pick 1, 2, 3, .... m coins from the remaining pile. Next A, followed by B, so on...

In the process, the player who makes last move (picks all remaining coins <= m from the pile) is the winner.

Now, given N = 15, m = 3, and A starts the game with some 1 <= x <= m coins. How many different ways are there that A can win the game?

Hint: Use state space analysis method (i.e. trees).