Nim Sum Game (Game Theory)

Revision en1, by Saksham_Sahgal, 2022-08-11 21:22:52

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

Tags xorsum, nim games, game theory


  Rev. Lang. By When Δ Comment
en1 English Saksham_Sahgal 2022-08-11 21:22:52 2530 Initial revision (published)