Multi-Nim游戏结论不变证明
2024-08-29 13:07:51
Nim取石子游戏结论:
若n堆石子的异或和为0,则先手必胜;否则,先手必败
加入新规则:
每次取完石子后,可以将取的那一堆的石子 分为多堆,也可以不分
结论:
同Nim取石子游戏结论
证明:
如果异或和不为0,那先手不用分某一堆石子,同Nim游戏
如果异或和为0,
不执行分裂操作则先手必败,同Nim游戏
若执行分裂操作,如果能够证明执行分裂操作的后继局面异或和依然不为0,那么结论成立
采用反证法,证明如果分裂后异或和为0 会 产生矛盾
a1^a2^a3^……^an=0, a1=a2^a3^……^an
假设我们取的那一堆是第1堆,取完之后还有b1个,b1<a1
将b1分为x+y
若x^y^a2^a3^……^an=0
则 x^y=a2^a3^……^an
所以x^y = a1
又因为异或是不进位的加法,所以x^y<=b1<a1
产生矛盾
最新文章
- DotNetOpenAuth使用笔记
- winform 窗体传值
- java中的三种取整函数
- SQL Server 中关于 @@error 的一个小误区
- chrome developer tool 调试技巧
- 实现LoadRunner多个场景的顺序执行(命令行)
- Django网站直接使用supervisor部署
- Phone List
- 初试jQuery EasyUI
- 响应式WEB设计
- 【POJ1151】【扫描线+线段树】Atlantis
- UML--建模
- 【转载】google搜索从入门到精通
- CMDB服务器管理系统【s5day90】:创建资产更新服务器硬盘信息
- bzoj3926: [Zjoi2015]诸神眷顾的幻想乡 后缀自动机在tire树上拓展
- Mosfet Bi-Directional Switch NMOS PMOS Back to Back
- NHibernate获取实体配置信息(表名,列名等等)
- C# 后台获取请求来源、文件下载
- 算法笔记_053:最优二叉查找树(Java)
- 【转】 Pro Android学习笔记(九一):了解Handler(5):组件生命