推数的奇偶性

sokoban

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

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

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