number of setbits in a number and a game based on setbits

Question

I was trying this problem on bits manipulation came through this one:

Beauty of a number is the number of set bits in that number. A and B start playing a game where there is number N written on the board,the player whose turn is to move goes to the board and writes a new number N-K where k<=N and beauty of K is 1.It is also important that beauty of N-K must be equal to beauty of N. Last player to successfully complete his move wins the game.

They both play the game optimally.

P.S. i am not looking for a code here.I want to know how to approach this?

Answer 1

It is a typical game theory problem. Players play optimally means that any player will make the move such that it maximizes it chance of winning (taking into account that when player 2 gets a chance he will also be willing to do the same).

Now in this case let us see what are the moves allowed:

As required the beauty of a number should remain same and the k should have beauty 1 i.e. only 1 bit set(for ex. 00000100)

For further illustration let us assume that we only have 8 bit number.

If you see closely, for beauty of N to remain same, the bit set in k is at the (one of the) index at which N has a 0 and 1 is at left adjacent to it. I will take an example:

Let us say N is 01010001. now k can be 00100000, 00001000. If you see N-k the beauty remains same. After the operation, you will notice that 1 moves to right and hence 0 moves to left. For example when N=01010001 and k=00100000 (N-k) = 00110001.

Also the ending position of the game will be such that all 0's are to the left and and all 1's are to the right(00000111). You can count the number of moves possible given a number N. If it is odd then the player starting wins otherwise he loses.

Now to count the number of such moves is simple enumeration problem.