最少马步函数

王守恩

hujunhua 发表于 2022-6-24 09:06
断头路更多，更长。
f(11,0)=f(0,11)=f(11,6)=f(6,11)=7,都到不了8
f(3,3)=f(7,7)=6，到不了7

以 \(a_{n}\) 表示 \(f(x,y)=n\) 的点数，还可以有通项公式吗？

hujunhua

王守恩 发表于 2022-6-24 12:47
以 \(a_{n}\) 表示 \(f(x,y)=n\) 的点数，还可以有通项公式吗？

统计图中的标数，前10项为
{1, 8, 32, 88, 192, 304, 372, 416, 472, 540}
按从f(x,y)≥8开始才没有断头路，应有\[
a_{n≥8}=472+(540-472)(n-8)=68n-72,
\]

王守恩

hujunhua 发表于 2022-6-24 09:06
断头路更多，更长。
f(11,0)=f(0,11)=f(11,6)=f(6,11)=7,都到不了8
f(3,3)=f(7,7)=6，到不了7

高丽象的最少象步数。\(f(x,0)\) 好像是这串数，没有通项公式。
0, 5, 4, 5, 2, 5, 2, 5, 4, 5, 4, 7, 4, 5, 6, 7, 6, 7, 6, 7, 8, 9, 8, 9, 8, 9, 10, 11, 10, 11, 10, 11, 12, 13, 12, 13, 12, 13, 14, 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`的非负路径 。

mathe

对于一般一步跳跃m*n矩形对角线的广义马，容易证明当且仅当(m,n)=1而且m,n奇偶不同时，广义马可以跳到任意一格。
从(0,0)出发到(x,y)格，显然步数不小于$\frac{|x|}{\max{m,n}}$ ,$\frac{|y|}{\max{m,n}}$ 以及$\frac{|x|+|y|}{m+n}$,等。
根据上述最大值的不同取值范围，可以将整个平面分割成8个部分。
另外还可以将所有格子进行黑白染色使得相邻格子不同色，得出广义马总是在两种不同颜色之间跳跃，从而得出到达每个格子需要步数的奇偶性是固定的。
上面最小步数不等式加上奇偶性判断，可以给出每个格子步数的一个下界。
一个合理的猜测是在离原点充分远的地方，这个下界就是准确步数。

王守恩

mathe 发表于 2022-6-26 22:32
对于一般一步跳跃m*n矩形对角线的广义马，容易证明当且仅当(m,n)=1而且m,n奇偶不同时，广义马可以跳到任意 ...

对于一步跳跃2*3矩形对角线的广义马，\(f(n,0)\)和\(f(n,n)=\)的最少步数分别是
f(n,0): 0, 5, 4, 5, 2, 5, 2, 5, 4, 5, 4, 7, 4, 5, 6, 7, 6, 7, 6, 7, 8, 9, 8, 9, 8, 9, 10, 11, 10, 11, 10, 11, 12, 13, 12, 13, 12, 13, 14, 15, ...
f(n,n): 0, 2, 4, 6, 4, 2, 4, 6, 6, 6, 4, 6, 6, 6, 8, 6, 8, 8, 8, 10, 8, 10, 10, 10, 12, 10, 12, 12, 12, 14, 12, 14, 14, 14, 16, 14, 16, 16, ...
f(n,0)从第14项开始，大周期为6，小周期为2，所以`f(n,0)=2\lfloor\frac{n+4}6\rfloor+\mod[n,2]`
f(n,n)从第9项开始，周期为5，带一个偏离值，所以`f(n,n)=\begin{cases}2\lfloor\frac{n+2}5\rfloor,&n\not\equiv0\pmod5\\\frac{2n}5,&n\equiv0\pmod5\end{cases}`

王守恩

王守恩 发表于 2022-6-27 15:18
对于一步跳跃2*3矩形对角线的广义马，\(f(n,0)\)和\(f(n,n)=\)的最少步数分别是
f(n,0): 0, 5, 4, 5, 2, ...

\(f(n,n)=2\lfloor\frac{n+4}{5}\rfloor+2del[5,n-4]\)

hujunhua

x≥0, y≥0（第1象限内）的f(x,y)公式推导

mathe

首先我们知道路径中不同步骤的顺序是不重要的。
其次一些对称的步骤是不需要同时出现的，如果{2,-1},{-2,1}同时出现，那么同时将它们减少一次不改变结果。
所以假设最优步骤里面存在{-2,1}(它减少了x),那么由于不存在{2,-1}, 充分多的最优步骤里面必然有足够的{2,1}或{1,2}来平衡。
那么如果{2,1}和{1,2}总步数不小于3时，我们就可以调整成不带{-2,1}的方案，比如
{-2,1}+3{2,1}={2,1}+{2,-1}+{1,2}+{-1,2}//{4,4}
{-2,1}+2{2,1}+{1,2}=2{-1,2}+{1,2}+{2,-1}//{3,5}
{-2,1}+{2,1}+2{1,2}=2{2,1}+2{-1,2}//{2,6}
{-2,1}+3{1,2}=2{-1,2}+{1,2}+{2,1}//{1,7}
类似应该就可以说明其它的方案也可以被相同步骤或更少步骤替换，就可以证明问题了。当然情况比较多，其实用计算机枚举会更加方便

mathe

15#我猜测最终只要距离充分远，预测值会等于精确值，虽然这个结果对于1x2马步成立，但是对于更大一点的都不成立。
但是如果统计两者差值的分布，还是挺有规律的。
比如如果我们统计一定范围内差值分布，会有
1x4:

1. Delta 0 count 1676
   
2. Delta 2 count 800
   
3. Delta 4 count 21
   
4. Delta 6 count 3

复制代码

1x6:

1. Delta 0 count 158530
   
2. Delta 2 count 74856
   
3. Delta 4 count 16524
   
4. Delta 6 count 66
   
5. Delta 8 count 21
   
6. Delta 10 count 3

复制代码

2x3:

1. Delta 0 count 219156
   
2. Delta 2 count 30839
   
3. Delta 4 count 5

复制代码

2x5:

1. Delta 0 count 122243
   
2. Delta 2 count 117126
   
3. Delta 4 count 10605
   
4. Delta 6 count 23
   
5. Delta 8 count 3

复制代码

3x4:

1. Delta 0 count 198286
   
2. Delta 2 count 51643
   
3. Delta 4 count 66
   
4. Delta 6 count 5

复制代码