just remember that a player is allowed to pick 1/4/9/16 and his aim is to leave zero sticks for the other player. then make a tree with possible combinations of moves and you'll see a lot of them get eliminated. it isn't very tedious. for example u know to start with that if player 1 picks 1 or 16, player 2 can make choices in a way that he wins, so work it out only with 4 or 9 in the first stage.
Thanks you so much Do Bats eat cats...What I was looking for...You just provide the link for that..
Thanks vasudha for your inputs but don't you think it takes time to make the tree n there is still chances that after making the tree you end up marking a wrong answer(due to mistake while making tree).....Just have a look the link provide by Do Bats eat cats...I can't think of a simple method than this....
Delhi School of Economics
Sinistral, I hope you checked the second link and not the first.
Just draw a table and think of this from the point of view of the first player.
If there are 1, 4, 9 and 16 matchsticks, the first player will win. Thus, these are the winning positions. Mark them "W".
Note that 2 is a losing position (the only possible play is 2 → 1 → 0).
This means that if player 1 can force player 2 choose from a pile of 2 matchsticks, he is guaranteed to win.
Player 1 can leave 2 matchsticks if he gets to choose from either 3, 6 or 11 matchsticks. So, these are winning positions for player 1 too.
Moving like this you can find all the winning positions yourself, if you know the losing positions. The problem is now finding all the losing positions.
You will find that the smallest number that is still unmarked in your table has to be a losing position. So, far it is the number 5 (note that all permissible moves from 5 lead to winning positions for the second player).
So, 6, 9, 14 are winning positions as well, and so on.