- 1、本文档共16页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
由感性认识到理性认识
——透析一类搏弈游戏的解答过程
一、 游戏 2
二、 从简单入手 2
三、 类比与联想 6
四、 证明 8
五、 推广 11
六、 精华 12
七、 结论 16
八、 总结 17
游戏
游戏A:
甲乙两人面对若干堆石子,其中每一堆石子的数目可以任意确定。例如图1所示的初始局面:共n=3堆,其中第一堆的石子数a1=3,第二堆石子数a2=3,第三堆石子数a3=1。两人轮流按下列规则取走一些石子,游戏的规则如下:
每一步应取走至少一枚石子;
每一步只能从某一堆中取走部分或全部石子;
如果谁无法按规则取子,谁就是输家。
图 1 游戏的一个初始局面
游戏B:
甲乙双方事先约定一个数m,并且每次取石子的数目不能超过m个;
其余规则同游戏A。
我们关心的是,对于一个初始局面,究竟是先行者(甲)有必胜策略,还是后行者(乙)有必胜策略。
下面,我们从简单入手,先来研究研究这个游戏的一些性质。
从简单入手
用一个n元组(a1, a2, …, an),来描述游戏过程中的一个局面。
可以用3元组(3, 3, 1)来描述图1所示的局面。
改变这个n元组中数的顺序,仍然代表同一个局面。
(3, 3, 1)和(1, 3, 3),可以看作是同一个局面。
如果初始局面只有一堆石子,则甲有必胜策略。
甲可以一次把这一堆石子全部取完,这样乙就无石子可取了。
如果初始局面有两堆石子,而且这两堆石子的数目相等,则乙有必胜策略。
因为有两堆石子,所以甲无法一次取完;
如果甲在一堆中取若干石子,乙便在另一堆中取同样数目的石子;
根据对称性,在甲取了石子之后,乙总有石子可取;
石子总数一直在减少,最后必定是甲无石子可取。
对于初始局面(1),甲有必胜策略,而初始局面(3, 3),乙有必胜策略。
局面的加法:(a1, a2, …, an) + (b1, b2, …, bm) = (a1, a2, …, an, b1, b2, …, bm)。
(3) + (3) + (1) = (3, 3) + (1) = (3, 3, 1)。
对于局面A, B, S,若S=A+B,则称局面S可以分解为“子局面”A和B。
局面(3, 3, 1)可以分解为(3, 3)和(1)。
如果初始局面可以分成两个相同的“子局面”,则乙有必胜策略。
设初始局面S=A+A,想象有两个桌子,每个桌子上放一个A局面;
若甲在一个桌子中取石子,则乙在另一个桌子中对称的取石子;
根据对称性,在甲取了石子之后,乙总有石子可取;
石子总数一直在减少,最后必定是甲无石子可取。
初始局面(2, 2, 5, 5, 5, 5, 7, 7),可以分成两个(2, 5, 5, 7),故乙有必胜策略。
对于局面S,若先行者有必胜策略,则称“S胜”。
对于局面S,若后行者有必胜策略,则称“S负”。
若A=(1),B=(3, 3),C=(2, 2, 5, 5, 5, 5, 7, 7),则A胜,B负,C负。
我们所关心的,就是如何判断局面的胜负。
如果局面S胜,则必存在取子的方法S→T,且T负。
如果局面S负,则对于任意取子方法S→T,有T胜。
设初始局面S可以分解成两个子局面A和B(分解理论)。
若A和B一胜一负,则S胜。
不妨设A胜B负;
想象有两个桌子A和B,桌子上分别放着A局面和B局面;
因为A胜,所以甲可以保证取桌子A上的最后一个石子;
与此同时,甲还可以保证在桌子B中走第一步的是乙;
因为B负,所以甲还可以保证取桌子B中的最后一个石子;
综上所述,甲可以保证两个桌子上的最后一个石子都由自己取得。
若A负B负,则S负。
无论甲先从A中取,还是先从B中取,都会变成一胜一负的局面;
因此,乙面临的局面总是“胜”局面,故甲面临的S是“负”局面。
若B负,则S的胜负情况与A的胜负情况相同。
若A胜B胜,则有时S胜,有时S负。
如果S=A+C+C,则S的胜负情况与A相同。
令B=C+C,则S=A+B且B负,故S的胜负情况与A相同。
图1所示的初始局面(3, 3, 1) = (3) + (3) + (1),与局面(1)的胜负情况相同。
图1中所示的初始局面(3, 3, 1)是“胜”局面,甲有必胜策略。
称一个石子也没有的局面为“空局面”。
空局面是“负”局面。
如果局面S中,存在两堆石子,它们的数目相等。用T表示从S中把这两堆石子拿掉之后的局面,则称“S可以简化为T”。
局面(2, 2, 2, 7, 9, 9)可以简化为(2, 2, 2, 7),还可以进一步简化为(2, 7)。
一个局面的胜负情况,与其简化后的局面相同。
三个局面(2, 2, 2, 7, 9, 9)、(2, 2, 2, 7)和(2, 7),胜负情况都相同。
不能简化的局面称为“最简局面”。
局面 (2, 7)是最简局面。
最简局面中不会有两堆相同的石子
您可能关注的文档
- 国外一村一品运动对中国发展现代农业借鉴.doc
- 国外全装修已进入成熟阶段.doc
- 国外印刷书写纸的分类.doc
- 国外引进种子、苗木检疫审批事项办事指南.doc
- 国外摄影大师介绍.doc
- 国外的盐产品介绍.docx
- 国外糖尿病治疗的新观点.doc
- 国外综艺节目概况[1].doc
- 国字笔画并类表国字笔画名称.doc
- 国学堂—重新发现,中医太美.doc
- 2024高考物理一轮复习规范演练7共点力的平衡含解析新人教版.doc
- 高中语文第5课苏轼词两首学案3新人教版必修4.doc
- 2024_2025学年高中英语课时分层作业9Unit3LifeinthefutureSectionⅢⅣ含解析新人教版必修5.doc
- 2024_2025学年新教材高中英语模块素养检测含解析译林版必修第一册.doc
- 2024_2025学年新教材高中英语单元综合检测5含解析外研版选择性必修第一册.doc
- 2024高考政治一轮复习第1单元生活与消费第三课多彩的消费练习含解析新人教版必修1.doc
- 2024_2025学年新教材高中英语WELCOMEUNITSectionⅡReadingandThi.doc
- 2024_2025学年高中历史专题九当今世界政治格局的多极化趋势测评含解析人民版必修1.docx
- 2024高考生物一轮复习第9单元生物与环境第29讲生态系统的结构和功能教案.docx
- 2024_2025学年新教材高中英语UNIT5LANGUAGESAROUNDTHEWORLDSect.doc
文档评论(0)