数学研发论坛

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

[讨论] 数字魔方

[复制链接]
发表于 2021-1-13 11:23:09 | 显示全部楼层
四阶还真是有所不同,我在27#的评论回复草率了。
四阶的点击转化矩阵\[
T=\begin{pmatrix}D&I&\\I&D&I\\&I&D&I\\&&I&D\end{pmatrix},\text{there }
D=\begin{pmatrix}1&1&\\1&1&1\\&1&1&1\\&&1&1\end{pmatrix},I=\begin{pmatrix}1&&\\&1\\&&1\\&&&1\end{pmatrix}\]
求逆时发现 `T` 是奇异的, 秩只有14。好在增广矩阵[T,1]的秩也是14。
所以虽然不是任意可解的,但对于可解者,可得全1至全16的任意解。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-1-14 13:24:47 | 显示全部楼层
扩展到m*n矩阵形式,可以参看 https://blog.emath.ac.cn/guandengyouxihesaoleiwenti/ 中函数g(a,b)
我们需要分析矩阵g(I+B,I)的可逆性。
如果设$\omega_{m+1}=\frac{\pi}{m+1}, \omega_n=\frac{\pi}{n+1}$
于是不可逆的充分必要条件是存在整数u,v,$1\le u \le m, 1\le v \le n$,使得$\cos(u\omega_{m+1})+\cos(v\omega_{n+1})=\frac1 2$
比如m=n=4时,有解$u=1,v=3$满足条件,所以不可逆。
而上面方程可以看成5个单位根之和为0的特殊情况,可以通过正多边对角线交点数目问题的分析过程(不超过12个单位根之和为0)找出所有解
https://bbs.emath.ac.cn/forum.ph ... 4584&fromuid=20
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-1-14 13:59:07 | 显示全部楼层
所以充要条件是在m+1和n+1一个为2的倍数,一个为3的倍数时或两者都是5的倍数时不可逆。
而当m=n时,充要条件是m+1和n+1都是5的倍数或都是6的倍数时不可逆

点评

对于本题不可逆的有4,5,7,9,11,12,13,14,16,17,19,23,24,25,27,29,30,31,32,34,35,37,39,41,42,43,44,47,49  发表于 2021-1-19 19:55
另外如果n+1是30的倍数,矩阵的秩差4满秩;而如果仅仅为5或6的倍数,那么秩差2满秩  发表于 2021-1-14 22:01
昨晚得到4, 5, 9, 11, 14, 17, 19, 23, 24, 29,...正莫明其妙  发表于 2021-1-14 15:30
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-1-15 08:17:40 | 显示全部楼层
T可以看成是$m\times m$的分块矩阵,每个分块是$n\times n$的小方阵。
假设有$mn$维向量\(x=\begin{pmatrix}x_1\\x_2\\\vdots\\x_m\end{pmatrix}\)使得$Tx=0$,其中每个$x_i$都是n维向量。
另外记n维向量$x_0=x_{n+1}=0$,于是我们有$x_{k+1}+Dx_k+x_{k-1}=0$
可以看出对比二阶切比雪夫多项式$U_{k+1}(x)=2x U_k(x)-U_{k-1}(x)$,
所以我们可以有$x_k = U_{k-1}(-\frac{D}2)x_1$
根据$0=x_{m+1}=U_m (-\frac{D}2)x_1$, 而且$x_m=U_{m-1}(-\frac{D}2)x_1$
可以得出$x_1$是方阵$U_m (-\frac{D}2)$特征值0对应的特征向量。
另外我们知道方阵$D-I$的特征值分别为$2\cos(\frac{k\pi}{n+1})=2\cos(k\omega_{n+1}), 1\le k\len$
于是在条件$1+2\cos(k\omega_{n+1})=-2\cos(s\omega_{m+1})$时,
取$D-I$特征值$2\cos(\frac{k\pi}{n+1})$对应的特征向量$y$,必然有$U_m (-\frac{D}2)y=U_m(\cos(s\omega_{m+1}))y=0$
所以我们可以取$x_1$为$2\cos(\frac{k\pi}{n+1})$对应的特征向量$y$,这时有$x_m = U_{m-1}(\cos(s\omega_{m+1}))y=\frac{\sin(s m\omega_{m+1})}{\sin(s\omega_{m+1})}$,其中s为偶数时$x_m=-x_1$,s为奇数时,$x_m=x_1$

而对于$D-I$的特征值$\lambda$对应的向量\(y=\begin{pmatrix}y_1\\y_2\\\vdots\\y_n\end{pmatrix}\),同样设$y_0=y_{n+1}=0$
$y_{k+1}=\lambda y_k -y_{k-1}$
而且显然这个递推式必然周期为n+1或2(n+1) ($y_{n+2}=-y_n$)
其中周期为n+1代表$y_1=y_{n+2}=-y_n$, 周期为2(n+1)代表$y_1=-y_{n+2}=y_n$
也就是向量要么头尾对称(颠倒后和自己相同),要么反对称(颠倒后变成方向相反的向量。
所以看上去31#hujunhua发现的性质是可以推广的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-1-15 17:43:51 | 显示全部楼层
34#发现s为偶数时有$x_m=-x_1$,于是根据递推关系可以得出$x_{m-1}=-Dx_m=Dx_1=-x_2$,
继续递推可以得出$x_{m-2}=-x_3,...$,于是我们可以得出$x_1+x_2+...+x_m=0$,于是向量x所有分量之和必然为0,而这个信息等价于T的各列的线性组合可以得出全1的向量,即31# hujunhua提到的性质。
在另外一方面,矩阵$D-I$各特征值分别为$2\cos(k \omega_{n+1}), 1\le k \le n$, 其中k为偶数时,其特征向量前后颠倒后也变成自身的相反数(反对称),k为奇数时,其特征向量颠倒后也是保持不变(对称)。

比如对于$5\times 5$阶矩阵\(\begin{pmatrix}0&1&0&0&0\\1&0&1&0&0\\0&1&0&1&0\\0&0&1&0&1\\0&0&0&1&0\end{pmatrix}\)
特征值-1.7320508075688772935274463415058723670,-1, 0, 1, 1.7320508075688772935274463415058723670
对应的特征向量分别为
\(\begin{pmatrix}1\\-1.7320508075688772935274463415058723670\\2\\-1.7320508075688772935274463415058723670\\1\end{pmatrix}\) (对称)

\(\begin{pmatrix}-1\\1\\0\\-1\\1\end{pmatrix}\)(反对称)

\(\begin{pmatrix}1\\0\\-1\\0\\1\end{pmatrix}\)(对称)

\(\begin{pmatrix}-1\\-1\\0\\1\\1\end{pmatrix}\)(反对称)

\(\begin{pmatrix}1\\1.7320508075688772935274463415058723670\\2\\1.7320508075688772935274463415058723670\\1\end{pmatrix}\)(对称)

同样可以得出在k为偶数时,每个向量$x_1,x_2,...,x_m$都满足颠倒后变成自身相反数,所以它们所有分量之和必然为0,也得出x的分量之和为0.
这是因为记\(J=\begin{pmatrix}0&0&0&\cdots&0&0&1\\0&0&0&\cdots&0&1&0\\0&0&0&\cdots&1&0&0\\\vdots&\vdots&\vdots&\cdots&\vdots&\vdots&\vdots\\0&0&1&\cdots&0&0&0\\0&1&0&\cdots&0&0&0\\1&0&0&\cdots&0&0&0\end{pmatrix}\)
于是$Jx$即代表把向量x颠倒以后的向量,而由于$D-I$的对称性,有$J(D-I)J=D-I$,而且$J J=I$
所以如果$Jx_1=sx_1$,那么$Jx_2=-JDx_1=-JDJ Jx_1=-s JDJx_1=-s Dx_1=s x_2$, $Jx_3 = J(-Dx_2-x_1)=-JDJ Jx_2-Jx_1=s(-JDJ x_2-x_1)=s(-Dx_2-x_1)=s x_3$,
...


34# 方程$1+2\cos(k \omega_{n+1})+2\cos(s \omega_{m+1})=0$的解只能是$1+2\cos(2h_1 \omega_{5h_1})+2\cos(4h_2 \omega_{5h_2})=0$或$1+2\cos(h_1 \omega_{2h_1})+2\cos(2h_2 \omega_{3h_2})=0$
总可以对应s或k至少有一个是偶数的情况,所以对于一般情况31# hujunhua提到的性质也总是可以满足的。


毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-1-15 21:00:10 | 显示全部楼层
发现上面的分析还有一个致命的问题,就是分析过程都是在实数域内进行的。而我们需要模$mn$的环上进行分析。

如果我们计算一下,可以找到m=4,n=3时,$g_4(B_3+I_3,I_3)$的行列式为-9,那么关于模12是不可逆的,所以这时前面的分析结果就不适用了。

而对于方阵,在m=7,n=7时,$g_7(B_7+I_7,I_7)$的行列式为-34391,是7的倍数,所以同样关于模49不可逆。
下一个是m=n=12时,$g_12(B_12+I_12,I_12)$的行列式为-133968364171875,是9的倍数,同样关于模144不可逆。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-1-16 09:36:20 | 显示全部楼层
  1. f(n,x)={local(g0,g1,g);g0=1;g1=x;for(u=2,n,g=x*g1-g0;g0=g1;g1=g);g1}
  2. mm(n)={local(m);m=matrix(n,n);for(u=1,n,m[u,u]=1);for(u=1,n-1,m[u,u+1]=m[u+1,u]=1);m}

  3. ? matdet(f(7,mm(7)))
  4. %52 = -34391
  5. ? matdet(f(12,mm(12)))
  6. %55 = -133968364171875
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-1-16 10:03:47 | 显示全部楼层
现在回到最初始的题目,如果我们不求最优解,是否能够比较简单的人工方法找出一个解呢?
由于我们已经知道对于$3\times 3$的情况,总是有解,而且最终目标可以选定为任意数,我们先总是可以将前两行转变为相同的数
比如1#的题目
9 5 6
6 7 7
8 2 3
我们可以先点中间4下,变成
996
122
863
然后点右中格3下,变为
999
155
866
然后点左下格8下,变为
999
945
766
中下格5下,变为
999
995
322
右下格4下,变为
999
999
366
所以我们只要能够学会保持上面两行所有数相等的情况,对最后一行进行调整的较简单方案即可。

搜索可以发现
./findm9 111111211
Input:
1 1 1
1 1 1
2 1 1
Best move time 5
Candidate move:
Increase (1,1)
2 2 1
2 1 1
2 1 1
Increase (1,2)
3 3 2
2 2 1
2 1 1
Increase (2,3)
3 3 3
2 3 2
2 1 2
Increase (3,1)
3 3 3
3 3 2
3 2 2
Increase (3,3)
3 3 3
3 3 3
3 3 3
所以通过按(1,1),(1,2),(2,3),(3,1),(3,3)这五格(记为方案W)可以让其它所有格子同步加2而左下角格子仅加一(相对减一)。

./findm9 111111101
Input:
1 1 1
1 1 1
1 9 1
Best move time 3
Candidate move:
Increase (1,2)
2 2 2
1 2 1
1 9 1
Increase (3,1)
2 2 2
2 2 1
2 1 1
Increase (3,3)
2 2 2
2 2 2
2 2 2
说明通过按(1,2),(3,1),(3,3)这三格(记为方案T)可以实现其它格子都加一而中下格子加2(相对加1)的方案。


所以对于
999
999
366
我们需要先采用方案W三次,(5×3次)
变化为
666
666
633
方案T三次,(3×3次)
999
999
996
以及方案W的左右对称方案6次,得出(5×6次)
333
333
333
即可以让所有的数字相等,总共操作24+15+9+30=78次
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-1-16 10:06:21 | 显示全部楼层
另外如果考虑到方案W相对比较复杂,记忆更加困难,而方案T比较简单,我们还可以先调整4个角让它们数字相等,然后调整中心也和四个角相等,最后在四个方向分别采用方案T来达成目标。
比如1#的题目
9 5 6
6 7 7
8 2 3
点右上三次变为
989
671
823
左下一次变为
989
771
933
右下六次变为
989
777
999
点中间两次变为
919
999
929
然后使用T方案7次,变为
787
777
777
在使用T的上下对称的方案8次,变为
666
666
666
总共使用12+7×3+8×3=57次

点评

要的就是这个效果,不求最少次,求个简易玩法。  发表于 2021-1-16 10:45

评分

参与人数 2威望 +8 金币 +8 贡献 +8 经验 +8 鲜花 +8 收起 理由
王守恩 + 6 + 6 + 6 + 6 + 6 挺好!!!
aimisiyou + 2 + 2 + 2 + 2 + 2 很给力!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-1-16 10:47:59 | 显示全部楼层
本帖最后由 aimisiyou 于 2021-1-16 10:56 编辑
mathe 发表于 2021-1-16 10:03
现在回到最初始的题目,如果我们不求最优解,是否能够比较简单的人工方法找出一个解呢?
由于我们已经知道 ...


我初步就是走这个路线,前六个调整到一样(这里可以考虑如何用最少步数,你是用了24步调为6个9,可否用更少的步数调成6个*),但最底下三个就不知怎么玩了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2021-3-3 16:45 , Processed in 0.071648 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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