无

• 题型

  >

  组合数学

  >

  组合极值

情形一若 $(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}$$

考虑到坐标系的对称性，不妨设 $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}$$