sokoban 发表于 2009-6-21 23:16:38
——
今天看 Yahoo Sokoban Group 的老帖子，看到2001 年10月份，Lu Junjie 提出的一个有趣的结论：对于给定的一个关卡，在所有不同的解法中，推数要么总是奇数，要么总是偶数。
Lu Junjie 先给出了一个基于对换的证明。然后 Francois Marques 基于对格子像国际象棋棋盘那样黑白染色的方法，给出了一个简化的证明。
也许大家都知道这个结论。若第一次看到的话，想想也挺有意思的。
————————————————————
vincentlamar 发表于 2009-6-21 23:40:48
——
好证啊，黑到白是奇数，黑到黑或白到白是偶数

kexin_xiao 发表于 2009-6-24 20:45:12
——
以下问题可以借鉴
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。

骰迷 发表于 2009-6-27 19:34:59
——
欣然回帖又快又有水平，真是拜服。不過漏了貼上圖。 （注：欣然即“kexin_xiao”）
————————————————————
西北天狼 发表于 2009-10-31 22:47:07
——
最小异色格原理
一、染色
约定搬运工所在的位置唯一的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 发表于 2009-11-26 10:27:20 丨 8#
——
不尽其然，就第八期我就走出过奇数和偶数的答案。
————————————————————
migl 发表于 2009-11-26 11:43:44
——
回复 8# 的帖子
参照天狼的说法，
“除墙壁外就被染成了黑白相间的类国际象棋棋盘的颜色”
同一个关卡，过关时的步数视最后一个箱子的目标点颜色的不同而有奇有偶。
但是同一个关卡，过关时的推数必然同奇同偶。
发表于 2009-11-26 15:27:45 |只看该作者
应该是这样子的结论吧~ （注：天狼即“西北天狼”，后同）
[ 本帖最后由 migl 于 2009-11-26 11:45 编辑 ]
————————————————————
西北天狼 发表于 2009-11-26 15:27:45
——
米糕兄说的对，mengcheng兄答案的步数有奇有偶，证明了最后一个箱子所到的位置是不同（颜色）的，也就是说关卡有较大的回旋余地，对优化有帮助！（注：米糕即“migl”）
————————————————————
zhenying 发表于 2009-11-26 16:16:34
——
回复 8# 的帖子
关于推箱子的BP的奇偶不变性，自然会有许多人证明过。
读了kexin_xiao兄用几何学（还有代数学）证明过程、西北天狼兄用抽象代数学证明过程都是之，米糕兄的通俗说法更是容易理解的结论。
第八期BM出现奇偶两种不同解答，那是因为最后到位的目标点不同，BM的奇偶性与最后到位的目标坐标相关联或者说最后到位的目标点决定BM的奇偶性。
第七期BM必然是偶数，那是因为完成最后到位的目标点处在封闭的状况下只有一种可能。
这一证明具有一定的实际意义，为寻找最少BM创造了一种可能。

这是非常好和有用的sokoban资料。 知道推数的奇偶性， 如果你知道自己的答案是
100步推动，同样的关卡， 别人是不可能推出99步或者101步推动的答案。