Can someone explain the logic [and formal proof why this logic works] to solve this problem?
Consider a heap of N objects. Two players take turns playing the following game:
At his very first move, the first player removes from the heap between 1 and N-1 objects After that, at each step the player to move can remove any number of objects between 1 and the number of objects removed by the other player at the previous move When the heap becomes empty, the player to move loses the game.
I know that removing the number of objects from Last on bit works. The Last on-bit, I mean the below.
int k=0; while( n % (1<<(k+1)) == 0) k++; printf("%d",(1<<k)); fflush(stdout); n -= (1<<k);
I need a formal proof/Argument that why is this working. Or why this is guaranteed to work?