【算法笔记】Bouton定理

概述

对于NIM游戏,相信大家都知道一个结论:

每一堆石子的数量给异或起来,若为0则先手必败,否则先手必胜

这个结论就是Bouton定理。
但对于这个定理,我一直没有找到简洁的证明
今日再一次翻看《白书》,终于觅得,于是记录于此

Bouton定理的结论

对于原版的NIM游戏
若每队石子的个数的NIM和为0,则先手必败
否则,先手必胜

Bouton定理的证明

参见《算法竞赛·入门经典·训练指南》P135

后记

为什么感觉这么鬼畜…..
最关键的证明部分是一个引用QAQ
唉,懒癌晚期,放弃治疗…..
jslugcg9lhkh0ix9zh