最少马步函数

王守恩

如图，中国象棋的"马"位于一个很大棋盘的中心点（标着 0 ），枰点上标的数字表示"马"从中心到达该点所需的最少步数。

1、以棋盘中心点为原点，坐标轴平行于棋盘线路。函数`f(x,y)`表示点`(x,y)`上标的数字，求`f(x,y)`的表达式。
2、以`a_n`表示`f(x,y)=n` 的点数，图中已呈现出明显的周期性，可以得到：
\[a_0=1,a_1=8,a_2=32,a_3=68,a_4=96,a_{n≥5}=28n-20\]

yigo

一、最捷路径的表示

按2#的性质2的推论1，一条最捷路径总可以用任意4个独立方向(任意两个方向不相反）来表示，以下就取下述4个方向:\[(\bar1,2), (1,2), (2,1), (2,\bar1)
\]对于给定的 (x,y), 最捷路径Path(x,y)总可以表示为\[(x,y)=a(\bar1,2)+b(1,2)+c(2,1)+d(2,\bar1)\]写成分量形式即\[\begin{cases}
x=-a+b+2c+2d\\
y=\ 2a+2b+c-\ d\tag1
\end{cases}\]以后，最捷路径Path(x,y)我们用方程的解向量{a,b,c,d}来表示.

二、考虑对称性，只需求出0≤y≤x区域内的f(x,y)  的表达式

在这个区域内，感觉存在`a,b,c,d`皆非负的最捷路径（不知道怎么证明）。
如此，则有\[f(x,y)=\min(a+b+c+d)\tag2
\](1)的上下两式相加得 \[x+y=(a+d)+3(b+c)\tag3
\]则\[a+b+c+d=\frac{x+y+2(a+d)}3\tag4\]所以a+d取最小值时，f(x,y)最小。
令x+y除以3的余数为 r，那么 a+d=3s+r，s为非负整数。
对于给定的a, s，可求得b=(2y-x+12s+4r-9a)/3≥0,c=(2x-y+9a-15s-5r)/3≥0,
可得\[\frac{9a+x-2y-4r}{12}≤s≤\frac{9a+2x-y-5r}{15}\tag5
\]由不等式知，a越小，s的下限越低，
只要找到最小的a值，使得s是满足上面不等式的非负整数，取s的下限值，则为f(x,y)的解，
\[\begin{align}s&=\max\left(0,\left\lceil{\frac{9a+x-2y-4r}{12}}\right\rceil\right)\tag6\\
f(x,y)&=2s+\frac{x+y+2r}3\tag7\end{align}\]
当x+y>=15时，a都可以取0，此时$s=max(0,\ceil{(x-2y-4r)/12})$，
也就是说，$x+y>=15$时，不需要走(-1,2)的步法，即能实现最小值。\[
f(x,y)=\frac{x+y+2\mod(x+y,3)}3+\max\left(2\left\lceil\frac{x-2y-4\mod(x+y,3)}{12}\right\rceil,0\right)\tag8
\]经验算，公式在$x+y>=7$时得出的最小步数是对的，但是a=0，得到的b，c，d有负数解，可取a=1，不改变f(x,y)的解，在x+y>=15时，都成立。

hujunhua

yigo 发表于 2022-6-10 16:48
考虑对称性，只需求出0≤y≤x区域内的f(x,y)  的表达式即可.
在这个区域内，感觉存在a,b,c,d皆非负的最捷路径（不知道怎么证明）

下面就来证明，在x≥0,y≥0,f(x,y)≥5的情况下，Path(x,y)存在a,b,c,d皆非负的最捷路径{a,b,c,d}。

【事实1】$x≥0,y≥0,f(x,y)≥5->x+y>=7,x+2y>=7,2x+y>=7$.
       这是一楼的图中所见的事实。最小值取点于坐标轴上。

【命题1】`a≥0∨d≥0`, 即`a,d`至少有一个非负.
证明：用反证法。假定`a<0,d<0`, 由于`(a+d)+3(b+c)=x+y>0→b+c>0`,
所以Path(x,y)中存在片段`\{-1,0,1,-1\}=Path(1,0)`或者`\{-1,1,0,-1\}=Path(0,1)`
这都是长度为3的断头路。

【命题2】`a≤1∨d≤1`,即 `a,d`至少有1个不大于1.
证明：用反证法。假定`a>1,d>1`, 那么Path(x,y)中存在片断`\{2,0,0,2\}=Path(2,2)`
这是长度为4的断头路。

【命题3】`a=-1∨d=-1→b≥2∨c≥2，`
证明：若`a=-1`, 由2#的(1)式消去d可得\[\begin{split}5b+4c&=x+2y-3a\\&=x+2y+3\\&≥7+3=10\\→b≥2&∨c≥2\end{split}
\]对于`d=-1`亦可同理得证。
【推论】若a<0, 则路径中存在片段{-1,2,0,0}=Path(3,2)或者{-1,0,2,0}=Path(5,0), 从而可替换为{1,0,1,1}或者{0,1,0,2},使a≥0.
同理，对于d<0亦可以通过片段替换使得d≥0. 并且，替换不使得b,c由正变负。
【命题4】`b=-1→c≥2,c=-1→b≥2`
证明：用反证法。假定`b=-1,c≤1`.
由2#的(1)式可解得\[\begin{cases}a=\D\frac{x+2y-5b-4c}3≥\frac{7+5-4}3=8/3>2\\\D d=\frac{2x+y-4b-5c}3≥\frac{7+4-5}3=2\end{cases}\]由命题2知这不可能。
同理可证 `c=-1→b≥2`.
【推论】若b<0,则路径中存在片段{0,-1,2,0}=Path(3,0), 从而可替换为{1,0,0,2}, 使b≥0.
同理，对于c<0亦可以通过片段替换使得c≥0. 并且，替换不使得a,d由正变负。

综合命题3及其推论和命题4及其推论可知，存在`a≥0,b≥0,c≥0,d≥0`的非负路径 。

hujunhua

除了几个初值，1#的图中周期性很明显。
`f(±1,0)=f(0,±1)=3,f(±2,±2)=4`这 8 个异常的初值看似刺眼，但却可能是解题的钥匙。
马踏八方，分别为`(2,1), (1,2), (\bar1,2),(\bar2,1),(\bar2,\bar1),(\bar1,\bar2),(1,\bar2),(2,\bar1)`。
关于最捷路径，有以下几个性质。
【定义1】从(0,0)到(x,y)的最捷路径记为Path(x,y).
【性质1】一条Path(x,y)的步子顺序并不重要，它们的任一排列都能到达(x,y)。
【性质2】一条最捷路径中不能含有两个方向相反的马步。
        否则，按性质1，可以将这两个方向相反的马步调序至相邻而消除。
【推论1】一条最捷路径最多含有4种独立方向的马步。
【推论2】如果一条最捷路径分别含有某4种独立方向的马步a,b,c,d步，则共有`\D\frac{(a+b+c+d)!}{a!b!c!d!}`条同步异序路径。
【定义2】`f(±2,±2)=4`的这四点到不了标着5的点，故(±2,±2)称为断路点, 相应的路径Path(2,2)称为断头路。
断头路Path(2,2)有以下 4 条：

1、`(\bar2,1)+(2,1)+(1,2)+(1,\bar2)=(2,2)`
2、`.......2(2,1)+(\bar1,\bar2)+(\bar1,2)=(2,2)`
3、`(2,\bar1)+(\bar2,\bar1)+2(1,2).......=(2,2)`
4、`2(2,\bar1)+............+2(\bar1,2)=(2,2)`

从`(±1,0),(0,±1)`只能进到`(±2,±2)`, 故最终也是断路点，相应的路径亦属于断头路。
【性质3】一条步数大于5的最捷路径不可能含有一条断头路的所有步子。
【性质4】Path(x,y)的任意子集都是一条较短的最捷路径。

hujunhua

最捷路径, 以下沿用3#的表示方法。

Path(x,y)往往不止一条最捷路径，假定f(x,y)=n.
我们把Path(x,y)的两条不同路径 中相同的步子一一去掉，直到两者无相同步子，假定最终各去掉了m步.
按2#的性质4，假定剩下的余集为Path(x',y'), f(x',y')=n-m. 这样含双路的Path(x',y')称为无重最捷双路。
编程计算表明，在第1象限只有以下14个无重最捷双路：
                                                              
Path(3,0): { 1,0,0,2}↔{ 0,-1,2, 0}, Path(0,3): {2,0, 0, 1}↔{ 0,2,-1, 0}
Path(5,0): { 0,1,0,2}↔{-1, 0,2, 0}, Path(0,5): {2,0, 1, 0}↔{ 0,2, 0,-1},
Path(3,2): {-1,2,0,0}↔{ 1, 0,1, 1}, Path(2,3): {0,0, 2,-1}↔{ 1,1, 0, 1},
Path(5,1): {-1,2,0,1}↔{ 0,-1,3, 0}, Path(1,5): {0,3,-1, 0}↔{ 1,0, 2,-1},
Path(4,4): {-1,3,0,0}↔{ 0, 0,3,-1},
Path(5,5): { 0,3,0,1}↔{ 1, 0,3, 0},
Path(9,3): { 0,3,0,3}↔{ 0,-1,5, 0}, Path(3,9): {3,0, 3, 0}↔{ 0,5,-1, 0},
Path(8,6): { 0,4,0,2}↔{ 0, 0,5,-1}, Path(6,8): {2,0, 4, 0}↔{-1,5, 0, 0}

另外，三条断头路也有无重双路
Path(1,0): { 0,1,-1, 1}↔{-1,0,1, -1}, Path(0,1): {-1,1,0,-1}↔{1,-1,1,0}
Path(2,2): {-1,1, 1,-1}↔{ 2,0,0,  2}, {0,2,-1,1}↔{1,-1,2,0}

无重双路能产生步子的组合替代，为分析Path(x,y)的性质提供方法

yigo

蓝色标注的点表示`a,b,c,d`同取非负值所达不到的，必须有所取负值。
红色标注的点是取a=0达不到的。
除了这些特殊点，3#最后的公式都能适用。
一些特殊点

王守恩

利用公式`a\pmod m=a-m\lfloor\frac am\rfloor，\lceil-a\rceil=-\lfloor a\rfloor`， 可以对3#最后的公式进行化简。
\[\begin{split} f(x,y)&=\frac{x+y+2(x+y)_{\pmod3}}{3}+\max\left(2\left\lceil\frac{x-2y-4(x+y)_{\pmod3}}{12}\right\rceil,0\right)....................(1)\\
&=x+y-2\lfloor\frac{x+y}{3}\rfloor+2\max\bigg(\left\lceil\lfloor\frac{x+y}{3}\rfloor-\frac{x+2y\ }{4}\right\rceil,0\bigg)\\
&=x+y-2\lfloor\frac{x+y}{3}\rfloor+2\max\bigg(\lfloor\frac{x+y}{3}\rfloor+\lceil-\frac{x+2y\ }{4}\rceil,0\bigg)\\
&=x+y-2\lfloor\frac{x+y}{3}\rfloor+2\max\bigg(\lfloor\frac{x+y}{3}\rfloor-\lfloor\frac{x+2y\ }{4}\rfloor,0\bigg)...................................(2)\\
&=x+y-2\min\left(\left\lfloor\frac{x+y}{3}\right\rfloor,\left\lfloor\frac{x+2y\ }{4}\right\rfloor\right).................................................(3)\\
&=\begin{cases}x+y-2\left\lfloor\frac{x+2y\ }{4}\right\rfloor,&0≤y<x/2\\
x+y-2\left\lfloor\frac{\ x+y\ }{3}\right\rfloor,&x/2≤y≤x\end{cases}...................................................(4)\end{split} \]

hujunhua

\[f(x,y)=x+y+2\left\lceil\frac{\abs{y-2x}+\abs{x-2y}-9(x+y)}{24}\right\rceil\]仅对`(0,1), (1,0),(2,2)`这3个断路点不成立。

王守恩

如图，中国象棋的"马"位于一个很大棋盘的中心点（标着 0 ），枰点上标的数字表示"马"从中心到达该点所需的最少步数。

把第 1 象限按 90° 分成 A,B,C 3 块。以 \(\tan(A)=\frac{1}{2}，\ \ \ \tan(C)=\frac{1}{2}，\)  中间是 B。

这样想：A,C 只要除以 2(每次走2步)，B 只要除以 3(每次走3步)。

A,  \(\D f(x,y)=\bigg\lceil\frac{x}{2}\bigg\rceil\)

B,  \(\D f(x,y)=\bigg\lceil\frac{x+y}{3}\bigg\rceil\)

C,  \(\D f(x,y)=\bigg\lceil\frac{y}{2}\bigg\rceil\)

编程验算，得数是 0 或 1。

Table[Table[x + y + 2 Ceiling[(Abs[x - 2 y] + Abs[y - 2 x] - 9(x + y))/24] - Ceiling[x/2], {x, 2 y - 2, 60}], {y, 0, 30}]

编程验算，得数是 0 或 1。

Table[Table[x + y + 2 Ceiling[(Abs[x - 2 y] + Abs[y - 2 x] - 9(x + y))/24] - Ceiling[(x + y)/3], {x, y, 2 y}],{y, 0, 30}]

编程验算，得数是 0 或 1。

Table[Table[x + y + 2 Ceiling[(Abs[x - 2 y] + Abs[y - 2 x] - 9(x + y))/24] - Ceiling[y/2],{y, 2x y - 2, 60}], {x, 0, 30}]

王守恩

如果把“马”换成朝鲜象棋（高丽象棋）的“象”呢？
朝鲜象棋的象是走“用”字的，它从中心(0,0)到达格点(x,y)最少步数又是怎样的图景呢？

hujunhua

断头路更多，更长。
f(11,0)=f(0,11)=f(11,6)=f(6,11)=7,都到不了8
f(3,3)=f(7,7)=6，到不了7
f(8,2)=f(2,8)=f(8,4)=f(4,8)=f(9,3)=f(3,9)=f(8,8)=6,只能到断路7
f(3,0)=f(0,3)=5,到不了6
f(1,0)=f(0,1)=f(5,0)=f(0,5)=f(5,2)=f(2,5)=f(5,4)=F(4,5)=f(6,1)=f(1,6)=f(6,5)=f(5,6)=f(7,0)=f(0,7)=5,只能到断路6
f(2,0)=f(0,2)=f(2,2)=f(1,3)=f(3,1)=f(4,2)=f(2,4)=4,只能到断路5
没有长度3及以下的断头路。