最少马步函数

王守恩

mathe 发表于 2022-6-29 10:05
首先我们知道路径中不同步骤的顺序是不重要的。
其次一些对称的步骤是不需要同时出现的，如果{2,-1},{-2,1 ...

当然情况比较多，其实用计算机枚举会更加方便。
以 \(a(n)\) 表示 \(f(x,y)=n\) 的点数，1x4 可以有通项公式吗？
更贪心一点：1x6,2x5,3x4 还可以有通项公式吗？手工是无法解决的。
手工可以出来 0x1：\(a(n)\)=1, 4, 8, 12, 16, 20, 24, 28, 32, 36, ...
就某个m×n来说：同一步数的外围圈，都是同一的八卦状。
，

王守恩

hujunhua 发表于 2022-6-29 01:24
x≥0, y≥0（第1象限内）的f(x,y)公式推导

粗糙一点的。

\(\D f(x,y)=x+y+2\left\lceil\frac{\ \abs{2x-3y}+\abs{3x-2y}-25(x+y)\ \ \ \ \ }{60}\right\rceil\)

\(\D f(m,n)=x+y+2\left\lceil\frac{\ \abs{mx-ny}+\abs{nx-my}-(m+n)^2(x+y)\ \ \ \ \ }{2*(m+n)(m+n+1)}\right\rceil\)

mathe

对于$m\times n$的广义马，其中(m,n)=1, m是偶数，从(0,0)移动到坐标(X,Y)的过程实际上给出了一组解
\(\begin{cases}X=u_x m+v_x n\\Y=u_y m+v_y n\end{cases}\)
其中$u_x, v_y, Y$同奇偶，$u_y, v_x, X$同奇偶。
反之，对于满足上面条件的解，我们可以通过\(g(u_x,u_y,v_x,v_y)=\max\{|u_x|,|v_y|\}+\max\{|u_y|,|v_x|\}\)步完成任务。

而根据中国剩余定理，对于任意的X,Y,我们必然可以找出整数解\(\begin{cases}X=u'_x m+v'_x n\\Y=u'_y m+v'_y n\end{cases}\), 只是$X,u'_y$不一定奇偶， $Y,u'_x$不一定奇偶。
如果$X,u'_y$不同奇偶，我们可以选择$u_y=u'_y+n, v_y=v'_y-m$,使得替换后$u_y,X$同奇偶；同样可以处理$u'_x$.
由此我们可以得到一组唯一的初始解
\(\begin{cases}X=u_x m+v_x n\\Y=u_y m+v_y n\end{cases}\)
其中$u_x, v_y, Y$同奇偶，$u_y, v_x, X$同奇偶,而且$-m\le v_x \lt m, -m\le v_y \lt m$。
对于上面的初始解，我们可以知道对于任意的整数$\lambda_1, \lambda_2$,
\(\begin{cases}X=(u_x+2\lambda_1 n) m+(v_x-2\lambda_1 m) n\\Y=(u_y+2\lambda_2 n) m+(v_y -2\lambda_2m) n\end{cases}\) 是所有符合条件的通解，于是我们的任务求变成求
\(\min_{\lambda_1,\lambda_2}\{ g(u_x+2\lambda_1 n, u_y+2\lambda_2 n, v_x-2\lambda_1 m, v_y -2\lambda_2m) \} = \min_{\lambda_1,\lambda_2} \{ \max\{|u_x+2\lambda_1 n|, |v_y -2\lambda_2m|\}+\max\{|u_y+2\lambda_2 n|,|v_x-2\lambda_1 m|\}\}\)
对于计算机来说，就是枚举各种不同组合（去除绝对值后分别枚举各种不同分支取最大值，得到一系列线性方程求解即可),
根据每项正负有$2^4=16$种可能，对于每种可能，两个max不同选择有2×2种，共需要分析16*4=64种情况，每种都提供了一组线性不等式约束并且目标只也是线性函数。需要逐一分析即可

王守恩

王守恩 发表于 2022-6-30 09:11
当然情况比较多，其实用计算机枚举会更加方便。
以 \(a(n)\) 表示 \(f(x,y)=n\) 的点数，1x4 可以有通项 ...

以 \(a(n)\) 表示 \(f(x,y)=n\) 的点数，
我们已经有 3 串数：
0x1：\(a(n)\)=1, 4, 8, 12, 16, 20, 24, 28, 32, 36, ...
1x2：\(a(n)\)=1, 8, 32, 68, 96, 120, 148, 176, 204, 232, ...
2x3：\(a(n)\)=1, 8, 32, 88, 192, 304, 372, 416, 472, 540, 608, ...
1x4 可以有吗？
更贪心一点：1x6,2x5,3x4 还可以有吗？手工是无法解决的。
要解决“最少马步函数”，先得知道这些点的分布，先得统计这些点的数量。

王守恩

王守恩 发表于 2022-7-1 16:51
以 \(a(n)\) 表示 \(f(x,y)=n\) 的点数，
我们已经有 3 串数：
0x1：\(a(n)\)=1, 4, 8, 12, 16, 20, 2 ...

以 \(a(n)\)  表示 \(f(x,y)\)  的点数，
我们已经有 3 串数：
0x1：=1, 4, 8, 12, 16, 20, 24, 28, 32, 36, ...
1x2：=1, 8, 32, 68, 96, 120, 148, 176, 204, 232, ...
2x3：=1, 8, 32, 88, 192, 304, 372, 416, 472, 540, 608, ...
1x4 : = 我还是没找到规律，可以肯定的是《整数序列在线百科全书(OEIS)》没有的。

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

上述数据显示了一个奇怪的现象，就是数列的不规则前段，部分取自同一个数列
A008412:1, 8, 32, 88, 192, 360, 608, 952, 1408, 1992, 2720，...
截取长度L(m,n)=m+n-1。
这个数列的通项是 `A_0=1, A_{n>0}=\frac{8n(n^2+2)}3`

王守恩

hujunhua 发表于 2022-7-4 02:59
0x1：1, `4, 8, 12, 16, 20, 24, 28, 32, 36, ..., a(n>0)=4n`
1x2：1, 8, 32, 68, 96, `120, 148, 17 ...

谢谢 hujunhua！

所有的数字串都有一个共同的特点(加黑的数):每个数都是前面一个数与后面一个数的平均数。