### Saksham_Sahgal's blog

By Saksham_Sahgal, history, 16 months ago,

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

## Conclusion -

Hence if xor is zero B Wins , else A wins

• +13

| Write comment?