数学研发论坛

 找回密码
 欢迎注册
查看: 339|回复: 30

[讨论] 最少马步函数

[复制链接]
发表于 2022-6-9 15:15:59 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
如图,中国象棋的"马"位于一个很大棋盘的中心点(标着 0 ),枰点上标的数字表示"马"从中心到达该点所需的最少步数。
最少马步图.png
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\]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-6-10 16:48:14 | 显示全部楼层

3# 0≤y≤x区域内的f(x,y)

一、最捷路径的表示

按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时,都成立。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 5 天前 | 显示全部楼层

13# 存在非负路径的证明

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`的非负路径 。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-6-10 03:09:25 | 显示全部楼层

2# 基本定义和性质

除了几个初值,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)的任意子集都是一条较短的最捷路径。


毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-6-11 00:27:05 | 显示全部楼层

4#可相互替代的最捷双路

最捷路径, 以下沿用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)的性质提供方法
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-6-11 10:18:06 | 显示全部楼层

5# 一些特殊点

蓝色标注的点表示`a,b,c,d`同取非负值所达不到的,必须有所取负值。
红色标注的点是取a=0达不到的。
除了这些特殊点,3#最后的公式都能适用。
一些特殊点
捕获1.PNG
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-6-13 14:00:45 | 显示全部楼层

6# 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} \]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-6-13 17:12:29 | 显示全部楼层

7# 在 `x≥0,y≥0`范围内的公式

\[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个断路点不成立。

评分

参与人数 1威望 +9 金币 +9 贡献 +9 经验 +9 鲜花 +9 收起 理由
王守恩 + 9 + 9 + 9 + 9 + 9 大神!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-6-16 11:25:05 | 显示全部楼层
如图,中国象棋的"马"位于一个很大棋盘的中心点(标着 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}]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-6-20 10:21:21 | 显示全部楼层
如果把“马”换成朝鲜象棋(高丽象棋)的“象”呢?
朝鲜象棋的象是走“用”字的,它从中心(0,0)到达格点(x,y)最少步数又是怎样的图景呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 7 天前 | 显示全部楼层

高丽象的最少象步图

断头路更多,更长。
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及以下的断头路。
最少象步图.png

评分

参与人数 1威望 +9 金币 +9 贡献 +9 经验 +9 鲜花 +9 收起 理由
王守恩 + 9 + 9 + 9 + 9 + 9 很给力!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2022-7-1 10:18 , Processed in 0.116831 second(s), 26 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表