最少马步函数

王守恩

如图，中国象棋的"马"位于一个很大棋盘的中心点（标着 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

1. {m,n}={7,2};
   
2. KnightStep={{-m,n},{m,n},{n,m},{n,-m},{m,-n},{-m,-n},{-n,-m},{-n,m}};
   
3. KnightMove[x_List]:=Append[x,Complement[Union@@Outer[Plus,Last@x,KnightStep,1],x[[-2]]]]
   
4. sites=Nest[KnightMove@#&,{{{0,0}},KnightStep},3];
   
5. sites=NestWhile[KnightMove@#&,sites,Differences[Length/@#,2][[-3;;-1]]!={0,0,0}&];
   
6. a=Length/@sites
   
7. {L=(Length@a)-6,d=Last@Differences@a,d(L+1)-a[[L+2]]}
   
8. ListPlot[sites,AspectRatio->Automatic, PlotMarkers->ToString/@Range[0,L+6]]

复制代码

0x1：1, `4, 8, 12, 16, 20, 24, 28, 32, 36, ..., a(n>0)=4n`
1x2：1, 8, 32, 68, 96, `120, 148, 176, ..., a(n>4)=28n-20`
1x4 : 1, 8, 32, 88, 192, 324, 448, 548, 620, `696, 788, 880, ..., a(n>8)=92n-132`
1x6 : 1, 8, 32, 88, 192, 360, 608, 900, 1184, 1444, 1664, 1828, 1952, `2104, 2292, 2480, ...,  a(n>12)=188n-340`
1x8 : 1, 8, 32, 88, 192, 360, 608, 952, 1408, 1924, 2432, 2916, 3360, 3748, 4064, 4292, 4476, `4728, 5044, 5360, ..., a(n>16)=316n-644`
1x10:1, 8, 32, 88, 192, 360, 608, 952, 1408, 1992, 2720, 3524, 4320, 5092, 5824, 6500, 7104, 7620, 8032, 8324, 8576, `8952, 9428, 9904, ..., a(n>20)=476n-1044`
2x3：1, 8, 32, 88, 192, 304, 372, 416, `472, 540, 608, ..., a(n>7)=68n-72`
2x5：1, 8, 32, 88, 192, 360, 608, 860, 1068, 1252, 1384, 1496, `1640, 1804, 1968, ..., a(n>11)=164(n-2)`
2x7：1, 8, 32, 88, 192, 360, 608, 952, 1408, 1864, 2260, 2636, 2964, 3228, 3428, 3632, `3896, 4188, 4480, ..., a(n>15)=292n-776`
2x9：1, 8, 32, 88, 192, 360, 608, 952, 1408, 1992, 2720, 3444, 4092, 4724, 5308, 5828, 6268, 6612, 6888, 7208, `7624, 8076, 8528, ..., a(n>19)=452n-1416`
3x4 : 1, 8, 32, 88, 192, 360, 608, 832, 960, 1040, 1112, 1212, `1332, 1456, 1580, ..., a(n>11)=124n-156`
3x8 : 1, 8, 32, 88, 192, 360, 608, 952, 1408, 1992, 2720, 3360, 3872, 4396, 4864, 5260, 5548, 5808, 6128, `6504, 6916, 7328, ..., a(n>19)=412n-1736`
4x5：1, 8, 32, 88, 192, 360, 608, 952, 1408, 1772, 1972, 2120, 2220, 2332, 2488, 2672, `2864, 3060, 3256, ..., a(n>15)=196n-272`
4x7：1, 8, 32, 88, 192, 360, 608, 952, 1408, 1992, 2720, 3288, 3692, 4140, 4420, 4608, 4848, 5112, `5432, 5788, 6144,..., a(n>17)=356n-976`
5x6：1, 8, 32, 88, 192, 360, 608, 952, 1408, 1992, 2720, 3244, 3520, 3768, 3928, 4060, 4224, 4448, 4708, 4980, `5260, 5544, 5828,...,a(n>19)=284n-420`

1x3：a(n)=1, 8, 32, 68, 96, 120, 148, 176, ..., 与1x2一致，只不过点坐标不同。
1x5 : a(n)=1, 8, 32, 88, 192, 304, 372, 416, 472, 540, 608, ..., 与2x3一致，也是点坐标不同。

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}&#8596;{ 0,-1,2, 0}, Path(0,3): {2,0, 0, 1}&#8596;{ 0,2,-1, 0}
Path(5,0): { 0,1,0,2}&#8596;{-1, 0,2, 0}, Path(0,5): {2,0, 1, 0}&#8596;{ 0,2, 0,-1},
Path(3,2): {-1,2,0,0}&#8596;{ 1, 0,1, 1}, Path(2,3): {0,0, 2,-1}&#8596;{ 1,1, 0, 1},
Path(5,1): {-1,2,0,1}&#8596;{ 0,-1,3, 0}, Path(1,5): {0,3,-1, 0}&#8596;{ 1,0, 2,-1},
Path(4,4): {-1,3,0,0}&#8596;{ 0, 0,3,-1},
Path(5,5): { 0,3,0,1}&#8596;{ 1, 0,3, 0},
Path(9,3): { 0,3,0,3}&#8596;{ 0,-1,5, 0}, Path(3,9): {3,0, 3, 0}&#8596;{ 0,5,-1, 0},
Path(8,6): { 0,4,0,2}&#8596;{ 0, 0,5,-1}, Path(6,8): {2,0, 4, 0}&#8596;{-1,5, 0, 0}

另外，三条断头路也有无重双路
Path(1,0): { 0,1,-1, 1}&#8596;{-1,0,1, -1}, Path(0,1): {-1,1,0,-1}&#8596;{1,-1,1,0}
Path(2,2): {-1,1, 1,-1}&#8596;{ 2,0,0,  2}, {0,2,-1,1}&#8596;{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及以下的断头路。