在无限方格网中，用木钉填满某条水平线上以及它下方的所有格子。合法操作与孔明棋相同：一枚木钉跳过相邻木钉，落在空格上，并移除被跳过的木钉。

这支军队希望向上前进。可以把木钉送到起始线上方的第一、第二、第三和第四行。

是否存在一组合法跳跃，能到达第五行？

提示

每次打开一个

尝试给每个格子赋予一个权重。

选择权重，使任意合法跳跃都不会增加总和。

解答

认真尝试后再打开

宝塔函数

设 $\phi =(1+\sqrt{5})/2$。根据某个格子到目标格的曼哈顿距离 $d$，赋予它权重 ${\phi }^{-d}$。

恒等式

$${\phi }^{-n}={\phi }^{-(n+1)}+{\phi }^{-(n+2)}$$

意味着：对于朝向目标的跳跃，落点的权重恰好等于两个被消耗位置的权重之和。其他方向的跳跃也不会增加总权重。

对位于第五行的目标格，所有初始木钉的权重总和严格小于目标格的权重。由于合法操作从不增加总和，任意操作序列都无法在那里放上一枚木钉。

第四行可以到达，第五行则不可以。证明的核心是一个 单调量：一个只能保持不变或减小的精心选取的量。