How to solve this? [Game theory]
Разница между en2 и en3, 374 символ(ов) изменены
Hello,↵

Can someone explain the logic [and formal proof why this logic works] to solve this problem?↵

[https://csacademy.com/contest/round-64/task/limited-moves/](https://csacademy.com/contest/round-64/task/limited-moves/)↵

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.↵

[UPD.]↵

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?↵

Thank you.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский RNR 2018-01-13 09:55:39 24
en3 Английский RNR 2018-01-13 09:54:53 374 Tiny change: 'he Last on bit I mean th' -> 'he Last on-bit, I mean th'
en2 Английский RNR 2018-01-13 09:35:03 40 Tiny change: 'the logic to solve ' -> 'the logic [and formal proof why this logic works] to solve '
en1 Английский RNR 2018-01-13 07:37:38 640 Initial revision (published)