Microsoft Interview Question Software Engineer / Developers
Country: India
Interview Type: Written Test
CEA
Let me explain this.
The key is to understand N%3.
Because everyone wants to get the status that there are 1 coins left, and the other one plays the next move. In this status, "I" can always win.
a)If the other played 1, I can play 2
b)If the other played 2, I can play 1.
And I can esure that everystep could be divided by 3,because i can always play "1+2" no matter you play 1, or you play 2.
So
a) IF N%3 = 0, i will play 2 first->(means n-2%3 = 1), and ensure all of next steps can be divided by 3
b)IF N%3 = 1, i can never win because i'm the first to play and b will ensure the each step could be divided by 3.
c)IF N%3 = 2 , i will play 1 and rest steps are exactly the same as a described.
Also, this game can be reduced to a similar game, where the goal is draw the last coin. Basically, you set aside the final coin. So the N=7 don't-get-stuck-with-the-coin game becomes the N=6 grab-the-last-coin game. To play the grab-the-last-coin game, you want to leave your opponent with 3 coins, and then they can't grab all of them, but they have to take one, leaving you with the last winning draw.
The strategy works for other variations of this game. Let's say users can draw 9 coins max, but they're compelled to draw at least 1, and the goal is to make the last grab. If I can leave you with 10 coins in that game, then I win. Likewise, I control you if I can stick you with 20, 30, 40, 50, 60 coins, etc. The first player always win that game, as long as the starting number of coins isn't an exact multiple of 10. (If the game starts with 100 coins, then player A is already under control by B.)
The loser sequence would be as bellow by proper play, if A plays first:
ABBABBABBABBA
A would be loser, only if its two predecessors are all Bs. Because whatever A takes 1 or 2, B now becomes the first player for the rest of the coins, and according the definition of the list, it would be its next player as the loser.
Let us assume Both are intelligent players.
If the coins count is 1+3n ... the B can definitely win the game with proper play..
In this case b has to draw coins based on coin selection of A
if(A selects 1coin)
b has to take 2 coins
else
b has to take 1 coin
Scenario 2 Coins count=1+3n+1 or 1+3n +2
A will win with proper play.
A need to offer round figure of 1+3n back to B to win the game.
if
B always wins. B responds with the opposite play of A, so that after B's first turn there are 4 coins, then after B's second turn there is 1 coin. B's strategy is the same for 10, 13, 16, etc.
- showell30@yahoo.com March 21, 2013A wins the variations on N=8 and N=9 by leaving 7 coins on the table after the first turn.