12
Nim Sum Game (Game Theory)
source link: http://codeforces.com/blog/entry/105883
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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.
-
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
</div
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK