推数的奇偶性

西北天狼

一、染色
    约定搬运工所在的位置唯一的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兄答案的步数有奇有偶，证明了最后一个箱子所到的位置是不同（颜色）的，也就是说关卡有较大的回旋余地，对优化有帮助！