智商吧 关注:203,458贴子:1,885,447

回复:抓枚游戏(Nim游戏,尼姆游戏)的扩展版,有兴趣吗?

只看楼主收藏回复

(续)
【三】证明上述第一条
即需要证明:
如果现状y1 ㈩ y2 ㈩……㈩ yn = 0,那么无论怎么抓,只要合规则,抓过以后必然
y1' ㈩ y2' ㈩……㈩ yn' ≠ 0。
证明如下(引用前面预备知识中介绍过的几个关系及交换、结合律):
y1' ㈩ y2' ㈩……㈩ yn'
=(y1 ㈩ y2 ㈩……㈩ yn)㈠ [(y1㈠y1')㈩(y2㈠y2')㈩……㈩(yn㈠yn')]
= 0 ㈠ [ d1 ㈩ d2 ㈩……㈩ dn ]
= ㈠ [ d1 ㈩ d2 ㈩……㈩ dn ]
这里的d1~dn是各堆抓前抓后枚数的影子数的相'㈠的差。
再根据前面:如果x ≠ 0则㈠x ≠ 0,
所以,只要证明d1 ㈩ d2 ㈩……㈩ dn ≠ 0 即可。
以下只要证明:各个d如此相㈩的总和的P进制形式中至少有一位不等于零,即可。
(待续)


IP属地:陕西45楼2017-01-22 23:40
回复
    (续)
    以下只要证明:各个d如此相㈩的总和的P进制形式中至少有一位不等于零,即可。
    按照抓枚的规则,可知d1~dn至少有一个至多有K个非零,其余都是零。故必存在一个最大的非零的d。
    因为影子数的P进制形式中各位只可能是1、0两种情况,故d的P进制形式中各位只可能是1㈠0 =1、1㈠1 =0、0㈠0 =0、0㈠1 =P-1,即只可能是以下三种:
    1、0、P-1
    而且,因为每堆抓后只可减小不可增加,以及影子数的保序性,所以各个d的P进制最高非零位只可能是1㈠0,不可能是0㈠1,故必为1。
    设最大的非零的d的最高非零位是第t位,则其他各个d的最高位或是第t位或低于第t位,那么,所有的各个d中,其第t位或为0,或为1。
    设第t位为1的d有m个,则必然1<m≤K<P 。
    于是相加的总和中,第t位应等于m。因1<m <P,不存在进位问题,所以第t位≠ 0。
    证毕。
    (待续)


    IP属地:陕西46楼2017-01-22 23:44
    回复
      (续)
      【四】证明上述第二条
      即需要证明:
      如果现状y1 ㈩ y2 ㈩……㈩ yn ≠ 0,那么一定存在一种合规则的抓法,能使抓过以后
      y1' ㈩ y2' ㈩……㈩ yn' = 0。
      证明如下:
      [为叙述简短,约定:凡称“第某位”者,对各X均指二进制形式的位,对各Y及E均指P进制形式的位。按影子数的定义,X和相应Y的“第某位”必相同。]
      按以下步骤即可实现此目的:
      用大写的X1~Xn以及Y1~Yn作为变量记号,开始令其分别等于x1~xn以及y1~yn,在以下步骤结束时的X1~Xn以及Y1~Yn即是这一步抓后的x1'~xn'以及y1'~yn'。
      用集合变量W代表此次抓时要改动的堆的集合。开始先令W为空集。
      (1) 计算出E=Y1 ㈩ Y2 ㈩……㈩ Yn。开始E必然≠ 0。
      (2) 设E的最高非零位是第T位,该位的值是m,则必然1<m≤K。
      (3) 因Y1~Yn的P进制每一位只可能是0或1,所以Y1~Yn中至少有m个的第T位为1,选择m个第T位为1的Y相应的堆(优先从W中选)。设所选的堆的集合为S;令W←W∪S (其中符号∪表示并集)。
      (4) 将集合S中各堆的X的二进制第T位原来的1改为0,第T位以下的所有位均改为1。显然改后的X必然比原来值减小。
      (5) 按改后的X1~Xn相应的Y1~Yn,重新计算E=Y1 ㈩ Y2 ㈩……㈩ Yn。此时E的第T位及更高的位必为零。
      (6) 如果E=0则结束。
      (7) 否则,重复执行(2)~(7)直到E=0结束。
      关于上述步骤,显然:
      一、因为重复中新的T必然低于旧的T,故有限次重复后必然出现E=0,可以得到结果。
      二、新的T必然低于旧的T,而先前旧的S中旧的第T位以下的位均已经改为1了,所以“选择m个第T位为1的Y所代表的堆”时只要遵循“优先从W中选”,就可以保证所有选过的S的并集W,不超出最大的一次的S。于是可以保证W内不超过K堆,符合规则。
      三、重复中每一次对X的改动都是减小,所以最后的结果也是减小,符合规则。
      所以,按照这个步骤,可以实现抓成“关键状态”的目的。
      证毕。


      IP属地:陕西47楼2017-01-22 23:50
      回复
        因文字能力问题,本来打算,尽可能:不要太长,同时又不要有该说的没说到或没说清楚会引起误解的地方。但写下来发现,很失败。两者很难兼顾。
        所以请各位谅解。
        或许,有时间可以改写一个更直观形象些,比较容易理解的说明?


        IP属地:陕西48楼2017-01-23 11:00
        收起回复


          来自Android客户端49楼2017-01-23 23:27
          回复
            如果把“谁抓到最后一枚为赢”,改为“ 谁抓到最后一枚为输”,也就是说“谁迫使对方抓到最后一枚为赢”。
            那么,对策又该怎样设计呢?


            IP属地:陕西50楼2017-02-02 22:10
            回复
              复楼上飞虎兄:
              有了前面“谁抓到最后一枚为赢”的思路以后,再来考虑改为“谁抓到最后一枚为输”后的情况,说起来也不太复杂了。
              不妨就按我当初的思考过程来说一下,或许比直接说出结果更容易理解一些?
              (下面采用和上文同样的符号、术语和文字约定)
              当初先想到,这里的规则,其实等效的说法是“争取抓剩最后一枚”就算赢。而前面的算法中是“争取抓完”。
              既然前面的策略是争取抓成y1 ㈩ y2 ㈩……㈩ yn = 0,那么,
              这里的策略能不能就争取抓成 y1 ㈩ y2 ㈩……㈩ yn = 1呢?
              这个“关键条件”行不行,依然是需要证明以下三条。
              一、如果现状已经满足这个条件,那么无论下步怎么抓,抓后必然就不满足这个条件了。
              二、如果现状不满足这个条件,那么下步总存在一种抓法,可使抓后满足这个条件。
              三、得胜结局(剩最后一枚)也满足这个条件。
              三条中,第一条的证明和前面相似,不难;第三条显然成立。问题在于第二条。
              第二条,需要证明如果现状相㈩总和不等于1,能不能总能有办法抓成等于1。
              参考前面的证明过程可知(不难证明),在大多数情况下,只要相㈩总和大于1,或者:相㈩总和等于零且 y1 、 y2 、……、 yn 的最低位并非全零时,仍然是可以办到的。
              但是,万一对方给你留下一个相㈩总和等于零且 y1 、 y2 、……、 yn 的最低位全都是零,您要想使相㈩总和变为1,唯一的办法是给某一堆中加一枚。但规则规定只许减不许加。所以这就不可行了。
              (待续)


              IP属地:陕西51楼2017-02-06 16:53
              回复
                (续)
                然后再考虑,上面所说的“万一”的情况(相㈩总和等于零且 y1 、 y2 、……、 yn 的最低位全都是零),在开始有可能出现,但是在“残局”(所有堆的枚数都不大于1)的时候,这种“万一”就不可能出现了。
                因为,所有堆的枚数都不大于1的时候,y1 、 y2 、……、 yn就已经只有最低位了, 如果最低位全都是零,意味着对方已经输过了。
                因此,如果进入了残局阶段以后,可以采用争取抓成 y1 ㈩ y2 ㈩……㈩ yn = 1的策略,就能保证必胜了。
                于是,剩下需要考虑的就是:未到残局之前,采取什么策略,才能掌握由非残局进入残局的主动权,以及进入残局第一步能否做到y1 ㈩ y2 ㈩……㈩ yn = 1。
                (待续)


                IP属地:陕西52楼2017-02-06 18:03
                回复
                  (续)
                  然而不难证明:未到残局之前,只要采用等同于前面“谁抓到最后一枚为赢”中所述的策略,就可以实现这两条了。证明如下。
                  残局之前,只要采用争取抓成y1 ㈩ y2 ㈩……㈩ yn = 0的策略,就可以掌握由非残局进入残局的主动权。
                  要想由非残局一步进入残局,只有大于1的堆数在1~K(即1~P-1)之间才行,不难证明此时必然y1 ㈩ y2 ㈩……㈩ yn ≠ 0。
                  而按照前面的证明,只要开始可行,在残局之前只留给对方y1 ㈩ y2 ㈩……㈩ yn = 0的布局,是可以保证的。所以不可能留给对方“大于1的堆数在1~K之间”的情况。
                  也就是说,只要采取这个策略,就不会给对方留下由非残局一步进入残局的机会。因此这种机会只可能留给己方。
                  当己方遇到这种机会的时候,如果继续采用原策略,就可以进入残局且y1 ㈩ y2 ㈩……㈩ yn = 0了。此时必然有1~K堆是由原不小于2的枚数抓成零或者1。
                  此时,只要将这1~K堆中,其中有一堆按原策略该抓完改为留下一个,或者有一堆按原策略该留下一个改为抓完,就可以实现y1 ㈩ y2 ㈩……㈩ yn = 1了,而且抓后依然属于“残局”,且改后的抓法符合规则。
                  因此,这种分阶段的策略是可行的。
                  综上所述:改为“谁抓到最后一枚为输”,也就是说“谁迫使对方抓到最后一枚为赢”这种情况下的策略是:争取抓成符合以下“关键条件”的布局
                  (非残局,且y1 ㈩ y2 ㈩……㈩ yn = 0)或者(残局,且y1 ㈩ y2 ㈩……㈩ yn = 1)
                  其中:“残局”指:“各堆的枚数均不大于1”。
                  其中:“y1 ㈩ y2 ㈩……㈩ yn = 1”可以改为“非零的堆数除以P余1”。


                  IP属地:陕西53楼2017-02-06 21:04
                  收起回复
                    会算的谁先谁胜


                    IP属地:广东54楼2017-10-06 16:33
                    回复
                      【发现上面证明过程中的一个细节错误,在53楼中,更正如下】
                      【原文】
                      当己方遇到这种机会的时候,如果继续采用原策略,就可以进入残局且y1 ㈩ y2 ㈩……㈩ yn = 0了。此时必然有1~K堆是由原不小于2的枚数抓成零或者1。
                      此时,只要将这1~K堆中,其中有一堆按原策略该抓完改为留下一个,或者有一堆按原策略该留下一个改为抓完,就可以实现y1 ㈩ y2 ㈩……㈩ yn = 1了,而且抓后依然属于“残局”,且改后的抓法符合规则。
                      因此,这种分阶段的策略是可行的。
                      【应更正如下】
                      当己方遇到这种机会的时候,如果继续采用原策略,就可以进入残局且y1 ㈩ y2 ㈩……㈩ yn = 0了。此时必然有1~K堆是由原不小于2的枚数抓成零或者1。
                      此时:
                      如果这1~K堆中,其中至少有一堆按原策略该抓成零的,则只要将其改为留下一个,就可以实现y1 ㈩ y2 ㈩……㈩ yn = 1了。
                      如果这1~K堆按原策略全是该抓成1的,那么此时按原策略抓后的局面必然存在至少P=K+1个堆是1(否则,只有1~K个1,不可能满足y1 ㈩ y2 ㈩……㈩ yn = 0)。于是,只要改变抓法,将这P堆中的K堆(包括原抓过的1~K堆)抓成零,剩下一个1,就可以实现y1 ㈩ y2 ㈩……㈩ yn = 1了。
                      这两种情况改后的抓法都符合规则,且抓后依然属于“残局”。
                      因此,这种分阶段的策略是可行的。


                      IP属地:陕西58楼2018-04-16 15:44
                      回复