找回密码
 欢迎注册
楼主: aimisiyou

[讨论] 数字魔方

[复制链接]
发表于 2021-1-16 17:19:04 | 显示全部楼层
其实我们不需要限定输入数据为1~$n^2$, 而且模也不一定需要选择为$n^2$.
可以改为任意模,这样就可以变成关灯问题的一种扩展了。其中关灯问题限定了模为2。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-1-16 19:04:10 | 显示全部楼层
本帖最后由 小铃铛 于 2021-1-16 19:10 编辑

尽量减少记忆,1,3,5,7,9位取最大数字点定,剩下4个边块,按“T”字三个端点点击:
1.要求“T”字的一横的两个端点数字相同
2.每个端点的点击次数=把“T”字的交点数字点击成端点数字的次数
116.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-1-17 11:23:51 | 显示全部楼层
我们可以把问题扩展为对于一个$m\times n$的棋盘,每个格子里面有一个$0~M-1$的数字,每次操作可以将一个格子以及它相邻的所有格子中数据关于模M加一,目标是经过若干次操作后使得所有格子中的数据相等(或等于指定的数字)。
如果假设$M=p_1^{a_1}p_2^{a_2}\cdots p_t^{a_t}$,
我们可以
i)寻找出方案使得格子中所有数关于模$p_t^{a_t}$同余。
ii)寻找出方案使得i)变换后的结果再关于模$p_{t-1}^{a_{t-1}}$同余,并且将其中每个步骤重复$h_t$次,其中$h_t$是$p_t^{a_t}$的倍数并且除以$p_{t-1}^{a_{t-1}}$的余数为1. 于是经过这个替换后的步骤,所有的格子中数关于模$p_{t-1}^{a_{t-1}}p_t^{a_t}$同余.
依次类推下去,最终我们可以找到关于模$M$同余的变换方案。

所以上面的方案说明,是否存在关于模M的解,等价于是否对于所有的模$p_i^{a_i}$解都存在。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-1-17 13:39:26 | 显示全部楼层
现在我们分析模$M=p^a$的情况
如同34#,将T看成是$m\times m$的分块矩阵,每个分块是$n\times n$的小方阵。
假设有$mn$维向量\(x=\begin{pmatrix}x_1\\x_2\\\vdots\\x_m\end{pmatrix}, y=\begin{pmatrix}y_1\\y_2\\\vdots\\y_m\end{pmatrix}\)使得$Tx=y$,其中每个$x_i,y_i$都是n维向量。
另外记n维向量$x_0=x_{m+1}=0$,于是我们有$x_{k+1}+Dx_k+x_{k-1}=y_k, 1\le k\le m$
设$g_m(2x)$为m阶第二类切比雪夫多项式。
于是$x_2=y_1-Dx_1=g_0(D)y_1-g_1(D)x_1, x_3=y_2-Dx_2-x_1=y_2-Dy_1+(D^2-I)x_1=g_0(D)y_2-g_1(D)y_1+g_2(D)x_1, x_4=y_3-Dx_3-x_2=y_3-Dy_2+(D^2-I)y_1-(D^3-2D)x_1=g_0(D)y_3-g_1(D)y_2+g_2(D)y_1-g_3(D)x_1,...$
最终我们需要$0=x_{m+1}=g_0(D)y_m-g_1(D)y_{m-1}+...+(-1)^{m-1} g_{m-1}(D)y_1 +(-1)^m g_m(D)x_1$
于是我们知道,只要模$M$情况求出方程$g_m(D)x_1=g_{m-1}(D)y_1-g_{m-2}(D)y_2+...+(-1)^m g_0(D)y_m$中$x_1$的任意一个解,就可以依次计算出$x_2,x_3,...,x_m$.而且这也是原方程是否有解的充分必要条件。
链接https://blog.csdn.net/mathe/article/details/1143634 中给出了M=2时这个过程对应的算法。
所以现在问题归结为在模$M=p^a$下对n阶方程$H x_1=b$的求解过程,$H=g_m(D), b=g_{m-1}(D)y_1-g_{m-2}(D)y_2+...+(-1)^m g_0(D)y_m$。
可以如下计算
i) 寻找矩阵H中p次数最少的一个元素,通过行列交换,使得这个元素被交换到第一行第一列,
ii)将第一行乘上常数使得第一行第二列变成p的幂(模M的结果,包含$p^0=1$)。
iii)将第2~n行依次减去第一行的倍数使得它们第一列都是0.
iv)假设H中前k行消元过程都已经完成,这时前k列是对角线都是p的幂的上三角阵,而且含p的次幂依次不减
    在后n-k行后n-k列中找出含p的次数最少的元素,通过行列交换将这个元素交换到第k+1行k+1列的位置。
v)将第k+1行乘上常数使得第k+1行第k+1列变成p的幂(模M的结果,包含$p^0=1$)
vi)将第k+2~n行依次减去第k+1行的倍数使得它们第k+1列都是0.
vii)如果k+1<n,将k设为k+1,转到第iv)步继续,知道k+1=n,即所有行消元完成
最后我们将H变换为一个上三角阵$\bar{H}\bar{x}=\bar{b}$,对角线元素$h_1,h_2,...,h_n$全部是p的次幂而且次数依次不减。
于是这个方程有解的充分必要条件为$h_i | \bar{b}_i$, (其中$h_i=0$要求$\bar{b}_i=0$)。
而且如果$h_i=p^{u_i}$,(如果$h_i=1 <=> u_i=0$, 而如果$h_i=0=M=p^a <=> u_i=a$, 且$u_0\le u_1 \le u_2 \le \cdots \le u_n$)
那么方程的解的数目为$\prod_{i=1}^n h_i=p^{u_1+u_2+...+u_n}$

而如果M是更加一般的情况,对各个素因子依次求解判断,有解的充分必要条件是对每个素因子的幂都有解,而解的总数目就是各个素因子幂的解的数目的乘积。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-1-17 14:04:45 | 显示全部楼层
后面发的第三题只要14步就可以完成9个1了:
117.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-1-17 14:06:26 | 显示全部楼层
小铃铛 发表于 2021-1-17 14:04
后面发的第三题只要14步就可以完成9个1了:

./findm9 933778566
Input:
9 3 3
7 7 8
5 6 6
Best move time 14
Candidate move:
Increase (1,2)
1 4 4
7 8 8
5 6 6
Increase (1,2)
2 5 5
7 9 8
5 6 6
Increase (1,2)
3 6 6
7 1 8
5 6 6
Increase (1,2)
4 7 7
7 2 8
5 6 6
Increase (1,2)
5 8 8
7 3 8
5 6 6
Increase (1,2)
6 9 9
7 4 8
5 6 6
Increase (1,2)
7 1 1
7 5 8
5 6 6
Increase (2,1)
8 1 1
8 6 8
6 6 6
Increase (2,1)
9 1 1
9 7 8
7 6 6
Increase (2,1)
1 1 1
1 8 8
8 6 6
Increase (3,2)
1 1 1
1 9 8
9 7 7
Increase (3,2)
1 1 1
1 1 8
1 8 8
Increase (3,3)
1 1 1
1 1 9
1 9 9
Increase (3,3)
1 1 1
1 1 1
1 1 1

点评

步数基本上都20+,貌似中心块有数对的步数会增加。第一题情况特殊,只需要22步,下面的,除了第一题,其他帮我验证看看。  发表于 2021-1-17 15:54
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-1-17 15:55:22 | 显示全部楼层

中心块有数对的,貌似都需要步数25+
117-1.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-1-17 16:06:03 | 显示全部楼层
统计所有1-9各使用一次的情况
最少9次,最多35次:
cc[9]=504
cc[10]=360
cc[11]=216
cc[12]=864
cc[13]=1224
cc[14]=3528
cc[15]=4608
cc[16]=5184
cc[17]=8136
cc[18]=12600
cc[19]=16488
cc[20]=19008
cc[21]=24336
cc[22]=25920
cc[23]=33120
cc[24]=35712
cc[25]=34416
cc[26]=35136
cc[27]=29448
cc[28]=22752
cc[29]=20160
cc[30]=14040
cc[31]=6984
cc[32]=5400
cc[33]=2016
cc[34]=576
cc[35]=144
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-1-18 08:14:40 | 显示全部楼层
采用任意模以后,31#的性质就不一定成立了。
比如$2\times 2$的方阵,模3就不能把所有数字同步加1.
同样,$8\times 8$, $14\times 14$的方阵也不行
mbulb.zip (3.92 KB, 下载次数: 0)
附件中代码,有多种输入格式
i)
./mbulb MOD n
会使用模MOD, 对一个n*n的方阵,给出将全0变为全1需要的方案(如果存在,任给一个)
./mbulb MOD n m
会使用模MOD, 对一个n*m的矩阵,给出将全0变为全1需要的方案(如果存在,任给一个)
./mbulb filename
会从文件filename里面读数据,假设第一行为MOD n m, 然后后面n行,每行m个数,每个数0~MOD-1之间,给出将全0变为这个结果需要的方案
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-1-31 15:52:07 | 显示全部楼层
关灯游戏升级版。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-28 23:53 , Processed in 0.047254 second(s), 18 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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