由感性认识到理性认识

《由感性认识到理性认识》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、由感性认识到理性认识——透析一类搏弈游戏的解答过程张一飞由感性认识到理性认识——透析一类搏弈游戏的解答过程一、游戏2二、从简单入手2三、类比与联想6四、证明8五、推广11六、精华12七、结论16八、总结17-16-由感性认识到理性认识——透析一类搏弈游戏的解答过程张一飞游戏2游戏A：2甲乙两人面对若干堆石子，其中每一堆石子的数目可以任意确定。例如图1所示的初始局面：共n=3堆，其中第一堆的石子数a1=3，第二堆石子数a2=3，第三堆石子数a3=1。两人轮流按下列规则取走一些石子，游戏的规则如下：Ø每一步应取走至少一枚石子；

2、Ø每一步只能从某一堆中取走部分或全部石子；Ø如果谁无法按规则取子，谁就是输家。第一堆：a1=3第二堆：a2=3第三堆：a3=1图1游戏的一个初始局面2游戏B：Ø甲乙双方事先约定一个数m，并且每次取石子的数目不能超过m个；Ø其余规则同游戏A。我们关心的是，对于一个初始局面，究竟是先行者（甲）有必胜策略，还是后行者（乙）有必胜策略。下面，我们从简单入手，先来研究研究这个游戏的一些性质。一、从简单入手F用一个n元组(a1,a2,…,an)，来描述游戏过程中的一个局面。G可以用3元组(3,3,1)来描述图1所示的局面。@改变这个n

3、元组中数的顺序，仍然代表同一个局面。G(3,3,1)和(1,3,3)，可以看作是同一个局面。-16-由感性认识到理性认识——透析一类搏弈游戏的解答过程张一飞@如果初始局面只有一堆石子，则甲有必胜策略。&甲可以一次把这一堆石子全部取完，这样乙就无石子可取了。@如果初始局面有两堆石子，而且这两堆石子的数目相等，则乙有必胜策略。&因为有两堆石子，所以甲无法一次取完；&如果甲在一堆中取若干石子，乙便在另一堆中取同样数目的石子；&根据对称性，在甲取了石子之后，乙总有石子可取；&石子总数一直在减少，最后必定是甲无石子可取。G对于初始局

4、面(1)，甲有必胜策略，而初始局面(3,3)，乙有必胜策略。F局面的加法：(a1,a2,…,an)+(b1,b2,…,bm)=(a1,a2,…,an,b1,b2,…,bm)。G(3)+(3)+(1)=(3,3)+(1)=(3,3,1)。F对于局面A,B,S，若S=A+B，则称局面S可以分解为“子局面”A和B。G局面(3,3,1)可以分解为(3,3)和(1)。@如果初始局面可以分成两个相同的“子局面”，则乙有必胜策略。&设初始局面S=A+A，想象有两个桌子，每个桌子上放一个A局面；&若甲在一个桌子中取石子，则乙在另一个桌子中

5、对称的取石子；&根据对称性，在甲取了石子之后，乙总有石子可取；&石子总数一直在减少，最后必定是甲无石子可取。G初始局面(2,2,5,5,5,5,7,7)，可以分成两个(2,5,5,7)，故乙有必胜策略。F对于局面S，若先行者有必胜策略，则称“S胜”。F对于局面S，若后行者有必胜策略，则称“S负”。G若A=(1)，B=(3,3)，C=(2,2,5,5,5,5,7,7)，则A胜，B负，C负。G我们所关心的，就是如何判断局面的胜负。@如果局面S胜，则必存在取子的方法S→T，且T负。@如果局面S负，则对于任意取子方法S→T，有T胜

6、。-16-由感性认识到理性认识——透析一类搏弈游戏的解答过程张一飞2设初始局面S可以分解成两个子局面A和B（分解理论）。@若A和B一胜一负，则S胜。&不妨设A胜B负；&想象有两个桌子A和B，桌子上分别放着A局面和B局面；&因为A胜，所以甲可以保证取桌子A上的最后一个石子；&与此同时，甲还可以保证在桌子B中走第一步的是乙；&因为B负，所以甲还可以保证取桌子B中的最后一个石子；&综上所述，甲可以保证两个桌子上的最后一个石子都由自己取得。@若A负B负，则S负。&无论甲先从A中取，还是先从B中取，都会变成一胜一负的局面；&因此，乙

7、面临的局面总是“胜”局面，故甲面临的S是“负”局面。@若B负，则S的胜负情况与A的胜负情况相同。@若A胜B胜，则有时S胜，有时S负。@如果S=A+C+C，则S的胜负情况与A相同。&令B=C+C，则S=A+B且B负，故S的胜负情况与A相同。G图1所示的初始局面(3,3,1)=(3)+(3)+(1)，与局面(1)的胜负情况相同。G图1中所示的初始局面(3,3,1)是“胜”局面，甲有必胜策略。F称一个石子也没有的局面为“空局面”。@空局面是“负”局面。F如果局面S中，存在两堆石子，它们的数目相等。用T表示从S中把这两堆石子拿掉之

8、后的局面，则称“S可以简化为T”。G局面(2,2,2,7,9,9)可以简化为(2,2,2,7)，还可以进一步简化为(2,7)。@一个局面的胜负情况，与其简化后的局面相同。G三个局面(2,2,2,7,9,9)、(2,2,2,7)和(2,7)，胜负情况都相同。-16-由感性认识到理性认识——透析一类搏弈游戏