推数的奇偶性

sokoban

今天看 Yahoo Sokoban Group 的老帖子， 看到2001 年10月份，Lu Junjie 提出的一个有趣的结论：对于给定的一个关卡，在所有不同的解法中，推数要么总是奇数，要么总是偶数。

Lu Junjie 先给出了一个基于对换的证明。然后 Francois Marques 基于对格子像国际象棋棋盘那样黑白染色的方法，给出了一个简化的证明。

也许大家都知道这个结论。若第一次看到的话，想想也挺有意思的。

Osullivan

想想看，估计非常有难度~~~~~~~~~~~

vincentlamar

好证啊，黑到白是奇数，黑到黑或白到白是偶数

四川绵阳

我觉得很难啊    没那水平

kexin_xiao

1.中国象棋盘的任意位置有一只马，它跳了若干步正好回到原来的位置。问：马所跳的步数是奇数还是偶数？
  2.右图是某展览大厅的平面图，每相邻两展览室之间都有门相通。今有人想从进口进去，从出口出来，每间展览厅都要走到，既不能重复也不能遗漏，应如何走法？

  3.能否用下图中各种形状的纸片（不能剪开）拼成一个边长为99的正方形（图中每个小方格的边长为1）？请说明理由。

  4.用15个1×4的长方形和1个2×2的正方形，能否覆盖8×8的棋盘？
  5.平面上不共线的五点，每两点连一条线段，并将每条线段染成红色或蓝色。如果在这个图形中没有出现三边同色的三角形，那么这个图形一定可以找到一红一蓝两个“圈”（即封闭回路），每个圈恰好由五条线段组成。
  6.将正方形ABCD分割成n2个相等的小正方格，把相对的顶点A，C染成红色，B，D染成蓝色，其他交点任意染成红、蓝两种颜色之一。试说明：恰有三个顶点同色的小方格的数目是偶数。
  7.已知△ABC内有n个点，连同A，B，C三点一共（n＋3）个点。以这些点为顶点将△ABC分成若干个互不重叠的小三角形。将A，B，C三点分别染成红色、蓝色和黄色。而三角形内的n个点，每个点任意染成红色、蓝色和黄色三色之一。问：三个顶点颜色都不同的三角形的个数是奇数还是偶数？
  8.从10个英文字母A，B，C，D，E，F，G，X，Y，Z中任意选5个字母（字母允许重复）组成一个“词”，将所有可能的“词”按“字典顺序”（即英汉辞典中英语词汇排列的顺序）排列，得到一个“词表”：
  AAAAA，AAAAB，…，AAAAZ，
  AAABA，AAABB，…，ZZZZY，ZZZZZ。
  设位于“词”CYZGB与“词”XEFDA之间（这两个词除外）的“词”的个数是k，试写出“词表”中的第k个“词”。
练习12
  1.偶数。
  解：把棋盘上各点按黑白色间隔进行染色（图略）。马如从黑点出发，一步只能跳到白点，下一步再从白点跳到黑点，因此，从原始位置起相继经过：白、黑、白、黑……要想回到黑点，必须黑、白成对，即经过偶数步，回到原来的位置。
  2.不能。
  解：用白、黑相间的方法对方格进行染色（如图）。若满足题设要求的走法存在，必定从白色的展室走到黑色的展室，再从黑色的展室走到白色的展室，如此循环往复。现共有36间展室，从白色展室开始，最后应该是黑色展室。但右图中出口处的展室是白色的，矛盾。由此可以判定符合要求的走法不存在。

  3.不能。
  解：我们将 99×99的正方形中每个单位正方形方格染上黑色或白色，使每两个相邻的方格颜色不同，由于 99×99为奇数，两种颜色的方格数相差为1。而每一种纸片中，两种颜色的方格数相差数为0或3，如果它们能拼成一个大正方形，那么其中两种颜色之差必为3的倍数。矛盾！
  4.不能。
  解：如图，给8×8的方格棋盘涂上4种不同的颜色（用数字1，2，3，4表示）。显然标有1，2，3，4的小方格各有16个。每个1×4的长方形恰好盖住标有1，2，3，4的小方格各一个，但一个2×2的正方形只能盖住有三种数字的方格，故无法将每个方格盖住，即不可能有题目要求的覆盖。

  5.证：设五点为A，B，C，D，E。考虑从A点引出的四条线段：如果其中有三条是同色的，如AB，AC，AD同为红色，那么△BCD的三边中，若有一条是红色，则有一个三边同为红色的三角形；若三边都不是红色，则存在一个三边同为蓝色的三角形。这与已知条件是矛盾的。

  所以，从A点出发的四条线段，有两条是红色的，也有两条是蓝色的。当然，从其余四点引出的四条线段也恰有两条红色、两条蓝色，整个图中恰有五条红色线段和五条蓝色线段。
  下面只看红色线段，设从A点出发的两条是AB，AE。再考虑从B点出发的另一条红色线段，它不应是BE，否则就有一个三边同为红色的三角形。不妨设其为BD。再考虑从D点出发的另一条红色线段，它不应是DE，否则从C引出的两条红色线段就要与另一条红色线段围成一个红色三角形，故它是DC。最后一条红色线段显然是CE。这样就得到了一个红色的“圈”：

  A→B→D→C→E→A。
  同理，五条蓝线也构成一个“圈”。
  6.证：将红点赋值为0，蓝点赋值为1。再将小方格四顶点上的数的和称为这个小方格的值。若恰有三顶点同色，则该小方格的值为奇数，否则为偶数。在计算所有n2个小方格之值的和时，除A，B，C，D只计算一次外，其余各点都被计算了两次或四次。因为A，B，C，D四个点上的数之和是偶数，所以n2个小方格之值的和是偶数，从而这n2个值中有偶数个奇数。
  7.奇数。
  解：先对所有的小三角形的边赋值：边的两端点同色，该线段赋值为0，边的两端点不同色，该线段赋值为1。
  然后计算每个小三角形的三边赋值之和，有如下三种情况：
  （1）三个顶点都不同色的三角形，赋值和为3；
  （2）三个顶点中恰有两个顶点同色的三角形，赋值和为2；
  （3）三个顶点同色的三角形，赋值和为0。
  设所有三角形的边赋值总和为S，又设（1）（2）（3）三类小三角形的个数分别为a，b，c，于是有
  S=3a+2b+0c=3a+2b。（*）
  注意到在所有三角形的边赋值总和中，除了AB，BC，CA三条边外，都被计算了两次，故它们的赋值和是这些边赋值和的2倍，再加上△ABC的三边赋值和3，从而S是一个奇数，由（*）式知a是一个奇数，即三个顶点颜色都不同的三角形的个数是一个奇数。
  8.EFFGY。
  解：将A，B，C，D，E，F，G，X，Y，Z分别赋值为0，1，2，3，4，5，6，7，8，9，则
  CYZGB=28961，_XEFDA=74530。
  在28961与74530之间共有74530-28961-1=45568（个）数，词表中第45568个词是EFFGY。

骰迷

欣然回帖又快又有水平，真是拜服。
不過漏了貼上圖。

西北天狼

一、染色
    约定搬运工所在的位置唯一的0步是偶数，在关卡有解的前提下，搬运工必然在有限步内到达仓库的所有位置（允许穿越箱子），将偶数步到达的位置标记为黑色，将奇数步到达的位置标记为白色，这样整个仓库，除墙壁外就被染成了黑白相间的类国际象棋棋盘的颜色。
二、最小异色格原理
    假设有N个箱子，对箱子的起始点和目标点做一个简单的统计，
记a、b分别为起始点是黑白格的数目，c、d分别为目标点是黑白格的数目，则a+b=c+d=N，记|a-c|=|d-b|=P，P称为最小异色格数，P的奇偶性决定了推数的奇偶性。
    证明:
    因为将箱子从一个格子推动到另一个相同颜色的格子，推数为偶数，不改变总推数的奇偶性，所以我们只关心推动到异色格子的箱子数目，推数为奇数，改变总推数的奇偶性，为了叙述方便先考虑a≥c的情况，假设，仅仅是假设，将c个箱子从黑色起始点推到黑色的目标点，b个箱子从白色起始点推到白色的目标点，这样剩下a-c个箱子从黑色起始点推到了d-b白色目标点，所以a-c的奇偶性决定了总推数的奇偶性；当然c个黑色目标点的箱子不一定都来自黑色的起始点，如果有x个箱子是来自白色起始点，则必然又有x个箱子从黑色起始点推到了白色目标点（x≤c且x≤b），总共有2x+a-c个箱子推到了异色目标点，总推数的奇偶性仍然等同于a-c的奇偶性。同理当a≤c时，总推数的奇偶性等同于c-a的奇偶性。（证毕）
三、推论
    假设关卡完成时最后一个箱子到达的目标点的颜色是唯一的，那么移动数的奇偶性也是不变的（证明略）。
例1

本关两个黑色目标点被白色目标点包围，最后到达的为白色目标点，搬运工停在黑格上，移动数必然是偶数。
例2
第七期“鬼手杯”MF8 推箱子比赛关卡，可以验证最后一个目标点为白色，移动总数必然是偶数。

[ 本帖最后由 西北天狼 于 2009-10-31 22:48 编辑 ]

mengcheng

不尽其然，就第八期我就走出过奇数和偶数的答案。

migl

参照天狼的说法，

除墙壁外就被染成了黑白相间的类国际象棋棋盘的颜色

同一个关卡，过关时的步数视最后一个箱子的目标点颜色的不同而有奇有偶。
但是同一个关卡，过关时的推数必然同奇同偶。

应该是这样子的结论吧~

[ 本帖最后由 migl 于 2009-11-26 11:45 编辑 ]

西北天狼

米糕兄说的对，mengcheng兄答案的步数有奇有偶，证明了最后一个箱子所到的位置是不同（颜色）的，也就是说关卡有较大的回旋余地，对优化有帮助！