PROBLEM LINK:
Author: Manish Pathak
Tester: Manish Pathak
Editorialist: Manish Pathak
DIFFICULTY:
SIMPLE
PREREQUISITES:
Game Theory
PROBLEM:
Two Friends A and B playing a game.There is a pile of stones from which they have to pick some stones and when anyone of them will not be able to pick any stone then the opponent will win.They can pick 2,3,4 stones in a single move.A is starting the game.
EXPLANATION:
We will first find the loosing and winning state.So in this case the loosing states are 0 and 1 because if there will be 0 or 1 stone then no one will be able to pick any stones and the one having the chance to play and pick stone will lose the game.Winning states will be 2,3,4,5 and again 6 and 7 will be the loosing states.e.g.if N=7 then if A will pick 2,3 or 4 any number of stones then B will pick the maximum poosible and after that A will not be able to pick any stone and hence will loss.
So we can conclude that if N%6==0 or 1 then it’s a loosing state otherwise winning.
AUTHOR’S AND EDITORIALIST’S SOLUTIONS:
Author’s and editorialist’s solution can be found here