马走日 象飞田

原点处有一匹马,它第一步可以跳到 $(\pm 1,\pm 2)$,$(\pm 2,\pm 1)$ 这八个点中的任一点,问:此马跳到整点 $P(m,n)$ 的最少步数是多少.


分析与解 考虑到坐标系的对称性,不妨设$m\geqslant n\geqslant 0$.定义两个整点$A(x_1,y_1),B(x_2,y_2)$的距离$$AB=|x_1-x_2|+|y_1-y_2|.$$思考如何用最小步数将马从$P(m,n)$跳回原点.

情形一 $m=2n$.

由于每次移动到原点的距离最多减少$3$,因此至少需要$\dfrac{m+n}3$步,每一步都取$(-2,-1)$即可.

情形二 $n\leqslant m<2n$.

先利用$m-n$次$(-2,-1)$移动到$(2n-m,2n-m)$.此时

(1) 若$2n-m$是$3$的倍数,那么再经过$\dfrac{2n-m}3$次$(-2,-1)+(-1,-2)$就可以移动到原点,此时最少步数是$\dfrac{m+n}3$.

(2) 若$2n-m$模$3$余$1$,那么经过$\left[\dfrac{2n-m}3\right]$次$(-2,-1)+(-1,-2)$后到达$(1,1)$,再通过$2$次移动即可回到原点,此时最小步数是$\left[\dfrac{m+n}3\right]+2$.

(3) 若$2n-m$模$3$余$2$,此时由于$(2,2)$回到原点需要$4$步,因此除了$(m,n)=(2,2)$的情形之外,可以考虑回退一步后通过$3$次移动回到原点(比如退回到$(4,3)$,再通过$3$次移动$(4,3)-(3,1)-(2,-1)-(0,0)$到达原点),此时最小步数为$\left[\dfrac{m+n}3\right]+2$.

情形三 $m>2n$.

先利用$n$次$(-2,-1)$从$(m,n)$移动到$(m-2n,0)$.此时

(1) 若$m-2n$是$4$的倍数,那么经过$\dfrac{m-2n}2$次$(-2,-1)+(-2,1)$就可以移动到原点,此时最小步数为$\dfrac m2$.

(2) 若$m-2n$模$4$余$1$,此时由于$(1,0)$回到原点需要$3$步,因此除了$(m,n)=(1,0)$的情形外,可以考虑回退一步后通过$2$次移动回到原点,此时最小步数为$\left[\dfrac{m}2\right]+1$.

(3) 若$m-2n$模$4$余$2$,此时通过$\left[\dfrac{m-2n}2\right]-1$次移动后到达$(2,0)$,再通过$2$次移动回到原点,此时最小步数为$\left[\dfrac{m}2\right]+1$.

(4) 若$m-2n$模$4$余$3$,此时通过$\left[\dfrac{m-2n}2\right]-1$次移动后到达$(3,0)$,再通过$3$次移动回到原点,此时最小步数为$\left[\dfrac{m}2\right]+2$.

综上所述,此马跳到整点$P(m,n)$的最小步数可以按以下方式计算.将$\max\{|m|,|n|\}$看成新的$m$,将$\min\{|m|,|n|\}$看成新的$n$.

规则一 若$(m,n)=(1,0)$,则最小步数为$3$;若$(m,n)=(2,2)$,则最小步数为$4$.

规则二 若$m\leqslant 2n$且$m\neq 1$,则$$\begin{cases} \dfrac{m+n}3,&3\mid (m+n)\\ \left[\dfrac{m+n}3\right]+2,&3\nmid (m+n).\end{cases} $$

规则三 若$m>2n$且$m\neq 1$,则$$\begin{cases} \dfrac m2,&m-2n \equiv 0\pmod{4},\\ \dfrac{m+1}2, &m-2n \equiv 1\pmod{4},\\ \dfrac{m+2}2,&m-2n \equiv 2\pmod{4},\\ \dfrac{m+3}2,&m-2n \equiv 3\pmod{4}.\end{cases} $$

此条目发表在趣味数学分类目录。将固定链接加入收藏夹。

发表评论