作者 | 马丁加德纳
译者 | 谈详柏,谈欣
在纸上画一个
移动的规则是这样的：每一步都必须是一个跳步, 将一枚硬币跳过与之相邻的另一枚硬币, 跳到前方空着的点上去. 跳步可以向左或向右, 也可向上或向下, 但不准斜跳.
例如, 作为第一步, 第一行第四列上的那枚硬币可以向右跳到同一行第6列那个白点的位置；也可以向下, 跳到该列的第3个点.
所有的跳跃动作都类似于跳棋, 但只限于水平或垂直方向, 被跳过的硬币也不拿掉. 我们并不关心用什么样的操作步骤会得到最小步数, 而只是关心此种转移究竟能否办到.
现在要考虑3个问题:
A. 任务究竟能否完成?
B. 如果有一枚硬币从黑点处移走, 剩下的 14 枚硬币能不能跳到白点上去?
C. 如果从黑点处拿掉两枚硬币, 剩下的 13 枚硬币能否跳到白点上去?
这个问题的设计者是 IBM 公司华生研究中心的韦格曼 (Mark Wegman）. 它之所以特别有趣, 因为上述 3 个问题都能在 10 岁孩子所掌握的知识范围内, 通过“啊哈!灵机一动”的奇思妙想迅速予以解决.
下面让我们看看这灵机一动的奇思妙想.
解决这种跳棋游戏的窍门是观察图中特殊的几个点，看下图中9个黑点. 显然, 不管你怎样跳, 处于黑点位置的任一硬币只能跳到另一处黑点.
线上有6个黑点, 但线下只有3个. 因此, 根据鸽笼原理(抽屉原理), 线上必然会有3枚硬币无法到达线下. 把所有的硬币跳到线下的任务是没有办法完成的, 除非在左上方的三角形阵列中事先拿掉3枚硬币. 只要拿掉其中任意 3 枚, 把剩下的 12 枚硬币跳到线下就不难了.
施瓦兹来信指出,即使准许硬币斜跳或者沿着对角线走象步而不跳, 不可能的证明依然成立.
阿比纳利 (David J. Abineri) 则寄来了另一个不可能性的证明, 证明的基础依然是鸽笼原理.
将各个纵列编号为
这样一来, 不论横跳、直跳还是斜跳, 黑点处的硬币始终只能留在黑点的位置. 游戏开始时有9枚硬币占据黑点的位置, 但线下却只有6个黑点.
脚注
- 原文发布于《跳棋游戏与非欧几何》