Processing math: 100%

Problem #121

The Game of Fibonacci and Powers of Two

You are given a pile of stones. Two people play this game turn by turn. In any turn, a player can remove a number of stones from the pile, say X, such that X can be either a non zero Fibonacci number or a power of 2.

The person that empties the pile wins the game. Both the persons play optimally, i.e they try to make the best possible move that will help them win. If the number of stones in the pile varies between 1 and 10^6, in how many cases will the first player lose?

Contributed by Saharsh Luthra

Solved by 68 users

Log in to submit answers.

Is something wrong?

Maintaining a collection of high quality questions is our top priority. If, however, you do find an error, report the problem and we'll make sure it is reviewed soon.