概述
对于NIM游戏，相信大家都知道一个结论：
每一堆石子的数量给异或起来，若为0则先手必败，否则先手必胜
这个结论就是Bouton定理。
但对于这个定理，我一直没有找到简洁的证明
今日再一次翻看《白书》，终于觅得，于是记录于此
Bouton定理的结论
对于原版的NIM游戏
若每队石子的个数的NIM和为0，则先手必败
否则，先手必胜
Bouton定理的证明
参见《算法竞赛·入门经典·训练指南》P135
后记
为什么感觉这么鬼畜…..
最关键的证明部分是一个引用QAQ
唉，懒癌晚期，放弃治疗…..
F*ckin’ awesome things here. I’m very satisfied to see your post. Thanks so much and i am taking a look ahead to contact you. Will you kindly drop me a mail?
Fantastic website. Lots of useful information here. I am sending it to several friends ans also sharing in delicious. And certainly, thanks for your effort!