Saksham_Sahgal's blog

By Saksham_Sahgal, history, 16 months 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 .
  • 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.


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

| Write comment?