国际象棋吧 关注:23,762贴子:389,015

【Pudding】关于四个皇后不能控制整个棋盘的证明

只看楼主收藏回复

1L喂度娘娘。
本帖未见完结请勿插楼,未经允许禁止转载。


IP属地:江苏1楼2018-02-12 02:12回复
    2L前言。
    这个帖子的来源关乎于以前的一个帖。
    https://tieba.baidu.com/p/3238853661?red_tag=3312848686
    那个时候自己的数学思维还不够成熟,有一个很幼稚的证明。
    (当然现在也不成熟就是了。)
    最近重新把这个问题挖了出来,又请教了一些在数学系的学长和同学,最终有了这份证明。
    发出来是因为这应该也算是贴吧的一份宝贵资源吧。


    IP属地:江苏2楼2018-02-12 02:14
    回复
      证明如下。
      第一项工作是改造一下棋盘。

      区别在于给黑格分了深浅,之后叫做深色格和浅色格。
      接下来我们需要确认两个定理:
      1. 一个后能且仅能控制8个与所在格颜色异色的格子。
      2. 深(浅)色格的后至多能控制一行或一列中2个浅(深)色的格子。
      在此不做证明,结论显然。
      下面开始分不同情况讨论。
      A1:4后同色
      不妨假设4后同在黑格中,根据定理1,此时每个皇后只能控制8个白格,而棋盘上恰有32个白格,这要求每个皇后控制的白格不能重复。因此,4个皇后只能同在深色或浅色格中,并且不可能同在一行或一列。
      不妨假设4个皇后同在深色格,此时只需考虑剩下的16个浅色格。
      首先考虑左下角的浅色格,它要求必须有一个皇后在对角线上,而这些情况是可列的。
      B1:

      考虑g1格,必须有一个皇后在b6、d4、f2、h2中的一格。由于同行同列的限制,只能在d4放上皇后。

      此时没有皇后能控制e1格,因此不可能在b2。
      B2:

      考虑e1格,必须有一个皇后在b4、d2、f2、h4中的一格。由于同行同列的限制,只能在f2放上皇后。

      此时没有皇后能控制e7格,因此不可能在d4。
      B3:

      考虑a7格,必须有一个皇后在b6、b8、d4、f2中的一格。由于同行同列的限制并证明了d4不能放皇后,只能在b8放上皇后。

      此时没有皇后能控制a3格,因此不可能在f6。
      B4:

      考虑a7格,必须有一个皇后在b6、d4、f2、h2中的一格。由于同行同列的限制并证明了d4不能放皇后,只能在b6或f2放上皇后。这两种情况是对称的,因此合并为一种。

      此时没有皇后能控制e7格,因此不可能在h8。
      至此证明了没有合适的方法来控制a1格。
      这证明这样的4个皇后不能全部控制这16个浅色格。4后同在白格同理。至此证明,4个同色格的皇后不能控制整个棋盘。


      IP属地:江苏本楼含有高级字体3楼2018-02-12 02:27
      回复
        A2:3后同色
        不妨假设3后同在白格中,考虑深色格,控制的仅可能为以下四种情况:三行,两行一列,两列一行,三列。而浅色格情况相同。这说明,至少有一行(列)的深色格和一行(列)的浅色格,有至少三个格子未被控制。
        考虑最后一个在黑格的皇后,其要么在深色格,要么在浅色格。不妨假设在深色格,根据定理2,该后至多只能控制一行(列)中2个浅色格,因此无法控制所有的浅色格。而在浅色格同理,无法控制所有的深色格。
        3后同在黑格同理。至此证明,3个同色格及一个异色格皇后不能控制整个棋盘。


        IP属地:江苏本楼含有高级字体4楼2018-02-12 02:28
        回复
          A3:2后黑格及2后白格
          根据定理1,2个在白格的颜色至多控制两行两列的黑格。因此,至少有16个黑格未被控制,分布可能是两行(列)深色格和两列(行)浅色格各8格,或者三行(列)3个深色格和三列(行)3个浅色格各9格。
          先考虑前一种情况。不妨设余下的两后同在深色格,根据定理2,每个后至多控制每行(列)的2个浅色格,则两个后至多控制两行(列)的8个浅色格。所以这两个后所控制的不重复。
          不妨假设这些浅色格是两列,则这些情况是可列的。
          在列举前需要一个引理。
          引理1:存在横向或纵向相距奇数格的皇后一定无法控制整个棋盘。
          首先,两个同色格的皇后至多控制28个同色格,这是因为一个皇后至多控制17个同色格,第二个皇后因为在外一圈所以至多控制15个同色格,两个皇后共计4个交叉点,因此至多控制28个同色格。这也就等价于至少有4个无法控制的同色格。
          并且同时我们可以断言,这些无法控制的同色格与某个皇后形成类似于围棋中“大飞”的形状,即横(纵)向三格后纵(横)向一格。由于两个皇后保持横(纵)向的对称,这些同色格也会成对出现在同一行或同一列。
          不妨假设先放在黑格,则白格的后为了控制这些剩余的格被限制了行或列。然而,两个黑格的皇后仅能控制12个白格,并且有一个4x3的白格阵需要两个白格的皇后控制。被限制在这之外某行或某列的两个白后是无法做到的,只需将白格分为深浅色格,因为除去两个黑格的皇后共有6行,是一定存在至少两对相邻行的,再由定理2即可证。
          接下来开始列举。



          (特殊的一种,这种情况下没有满足条件的皇后。)





          这些均满足引理1的条件,不再证明。
          再考虑一个在深色格一个在浅色格的情况。其实这种情况是不需讨论的,因为在分布是两行(列)深色格和两列(行)浅色格各8格的情况下,给白色格分深浅,这两个皇后一定同在深色或浅色格,而我们证明了两个皇后同在深色或浅色格不能控制整个棋盘。


          IP属地:江苏本楼含有高级字体5楼2018-02-12 02:32
          回复
            再考虑第二种情况,此时仅需考虑一个在深色格一个在浅色格的情况,若同色则根据上面的证明,是无法控制整个棋盘的。
            还是考虑浅色格,此时两个白格的皇后一共控制7个浅色格,剩下的9个浅色格为3行3列。这3行3列只会为以下三种情况。
            C1:

            这9格被一个皇后全部控制。此时仅需放上最后一个在深色格的皇后。考虑h5格必然在h线,但f1格必然无法控制。
            C2:

            皇后控制了7格,剩下的两格在一条斜线上。显然另一个皇后应当在这条斜线上的深色格中,但b4和f8格无法同时控制。
            C3:

            无论皇后在哪一位置都至少有两格无法控制,且能找到两格,这两格不在一条斜线上,在此不一一列举。
            为了证明这一点,我们引入距离的概念,两格的距离为从一个格沿横向或纵向到达另一个格所需的最少格数。则我们可以证明这两格满足距离为4的倍数。
            然而若两浅色格距离为4的倍数且不在一条斜线上,是不可能被深色格里的皇后同时控制的。若深色格皇后同时控制这两个浅色格,因为深色格的皇后距离控制格总是4的倍数加2,但两浅色格必在深色格的同一侧,计算距离时会取直线缩短,将两个4倍加2合为一个,此时两浅色格的距离为4的倍数加2,因此有逆否命题为真,即结论。所以这9个格无法全部控制。
            其他所有情况,只考虑浅色格则为上述三种情况的镜像或旋转。因此所有情况讨论完毕。
            至此证明,2黑格后2白格后无法全部控制。
            至此全部情况讨论完毕,这证明了4个皇后无法控制全部棋盘。


            IP属地:江苏本楼含有高级字体6楼2018-02-12 02:36
            回复
              证明完了,怎么说呢emmm...
              算是填补了自己一桩心事?或者说了了一桩心愿?
              如有错误欢迎指正。
              END.


              IP属地:江苏7楼2018-02-12 02:38
              回复
                楼主深入钻研的精神值得敬佩嘿!看样子你是计算机系的还是数学系的啊


                8楼2018-02-12 04:43
                收起回复
                  @雨神教教主
                  我怎么不记得我还拿电脑枚举过这玩意儿。。


                  IP属地:北京来自Android客户端10楼2018-02-12 14:07
                  收起回复
                    这回是一份真正的数学证明了,进步很大。相信这个证明能很好地培养楼主的基本功。我不是数学系的,作为外行说说自己的想法: 这里所做的工作就是大力度的裁剪,把原本20万数量级裁剪到20的数量级,在这个问题中就可以不依赖于计算机了。裁剪+计算机枚举可以证明更复杂的命题,比如任何魔方可在小于等于20步还原


                    IP属地:美国来自Android客户端11楼2018-02-13 20:47
                    回复
                      有个游戏叫“八后同盘互不吃”,四个后肯定控制不了全盘!至少有四个盲点


                      IP属地:山东来自Android客户端12楼2018-03-06 07:19
                      收起回复
                        既然这么愿意做数学题,可以做做这一道题,八后同盘互不吃,一共有多少种可能性?


                        IP属地:山东来自Android客户端13楼2018-03-06 07:38
                        收起回复
                          这是一道很难的组合问题


                          来自iPhone客户端14楼2018-03-06 12:50
                          回复
                            第八章有研究这个问题
                            https://pan.baidu.com/s/1KcPvJu7c2Olr-d4vphrGNw


                            IP属地:上海15楼2018-05-14 11:40
                            回复


                              IP属地:上海16楼2018-05-14 11:44
                              回复