数字魔方

hujunhua

四阶还真是有所不同，我在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的任意解。

mathe

扩展到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

mathe

所以充要条件是在m+1和n+1一个为2的倍数，一个为3的倍数时或两者都是5的倍数时不可逆。
而当m=n时，充要条件是m+1和n+1都是5的倍数或都是6的倍数时不可逆

mathe

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发现的性质是可以推广的

mathe

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提到的性质也总是可以满足的。

mathe

发现上面的分析还有一个致命的问题，就是分析过程都是在实数域内进行的。而我们需要模$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不可逆。

mathe

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. 
   
4. ? matdet(f(7,mm(7)))
   
5. %52 = -34391
   
6. ? matdet(f(12,mm(12)))
   
7. %55 = -133968364171875

复制代码

mathe

现在回到最初始的题目，如果我们不求最优解，是否能够比较简单的人工方法找出一个解呢？
由于我们已经知道对于$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次

mathe

另外如果考虑到方案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次

aimisiyou

mathe 发表于 2021-1-16 10:03
现在回到最初始的题目，如果我们不求最优解，是否能够比较简单的人工方法找出一个解呢？
由于我们已经知道 ...

我初步就是走这个路线，前六个调整到一样（这里可以考虑如何用最少步数，你是用了24步调为6个9，可否用更少的步数调成6个*），但最底下三个就不知怎么玩了。