Saksham_Sahgal's blog

By Saksham_Sahgal, history, 6 weeks ago, In English

What is Nim Game and how it is played?

  • It is a game in which two players play optimally turn by turn .
  • In each turn a player can choose only one pile and remove any number of stones (at least one) from that pile.

  • The person who is unable to make a move looses , hence the player who makes the last move wins.

  • determine which player wins the game.


How to decide who will win?

  • To decide who will win the initial configuration of the piles matter.
  • If the xor of all elements of the array is non-zero , then person starting the game will win.

  • If the xor of all elements of the array is zero , then other person will win.

  • Proof


Why it works ?

  • if the xor if all elements is zero then if we make any moves , the xor of all elements will definitely become non zero .
Why?
  • If the xor of all elements is non zero , then we can either make the xor non-zero again , or make the xor zero.
  • There definitely exists atleast one way to make xor zero again.

Why?

How to reach the Conclusion -

Conclusion -

Hence if xor is zero B Wins , else A wins

 
 
 
 
  • Vote: I like it
  • +13
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Did a problem similar to this topic appeared in the recent Codechef starters?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, it was Chef & Cook Game from Starters 51.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes , it came in Codechef and I was unable to think of a solution during the contest , thats why I learned the topic and explained the same in the blog.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Also I was amazed to see how did the problem had 600+ submission on CC by the end of contest , while i myself found conversion of the problem statement to the original nim game really hard to come up with on my own.

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

The recent problem from starters 51 (Chef & Cook Game) was more specifically a variation of Nimble Game, which in itself is a variation of Game of Nim.