Tuesday, November 30, 2010

Biased game

2 players were playing a game in which they have n number of balls. In each chance a player can pick a ball in between a number 1 to k both inclusive. The player making the last move wins the game.
Given the number n & k and said that both players are clever enough and wish to win, predict the result of the game.

Approach:
All the biased games are predominately based on the symmetrical moves, this is no exception. How can one ensure the win ?
Lets start with the base case of (n+1) coins (Obviously with coins < n the first player has to win :))
Now irrespective of the number of coins picked by player 1, the second player can clear out all the coins. So if the 2nd player can ensure that the number of coins is n+1 at the end he is destined to win.
Now what if the coins > n+1
The player should ensure that when the turn of the other player comes there should be n + 1 coins. This can be safely ensure by having 2* (n+1) coins

So in short if the coins are of the factor of n + 1 then the 2nd player will win, else the 1st player will win

2 comments :

  1. if n is a multiple of k+1 then 2nd player wins otherwise 1st player wins.

    ReplyDelete