# 关灯问题

2005年1月lkrich7在csdn询问

$\begin{matrix} 0&1&1&0&1&0\\ 1&0&0&1&1&1\\ 0&0&1&0&0&1\\ 1&0&0&1&0&1\\ 0&1&1&1&0&0 \end{matrix}$

$\begin{matrix} 0&1&0&0&1&0\\ 1&1&1&0&1&1\\ 0&0&0&0&0&1\\ 1&0&0&1&0&1\\ 0&1&1&1&0&0 \end{matrix}$

1.矩阵的状态与按开关的顺序无关
2.如果某个开关按下了两次，那么就相当于取消了第一次的操作，也就是说没有开关需要按超过1次

mathe在14年将问题转载到数学研发论坛

# 扫雷算法问题

2007年10月pavelalex在csdn提问

zgg__提问: 那么地雷上填什么数字呢？
pavelalex要求：数字是它周围雷的数目。

# 二维递推数列求解

2007年11月goodenfeet在csdn提问
$f(x,y)=f(x-1,y)+f(x+1,y)+f(x,y-1)+f(x,y+1)$，求$f(x,y)$

# 算法分析

## 关灯问题最初分析

mathe通过把关灯问题看成有限域$F_2$上的线性变换 来提出初步有效的解决方案：

mathe提供了一个C程序 , 时间复杂度为$O(n^4)$,这是因为其中稀疏矩阵的乘法没有优化。

## 必然有方案关闭所有灯

Puzzle 2: for this problem, we are giving up the detailed information about how the lights are connected. We are left knowing only that the connections are reflexive and symmetric, and that our task is to go from all lights ON to all lights OFF. Lossers gives a short explanation of how to see that this is so. First, we define the obvious matrix A with 1's indicating which switches control which lights. The matrix is symmetric and has 1's on its diagonal.

Now it's equivalent to show that there is some strategy x of button pushing that can go from all lights OFF to all lights ON. But that's just asking if there is a vector x such that

$A x = d$,
where d is the vector of all 1's. That is equivalent to asking if d is in the column space of A. And that is equivalent to asking if the "perpendicular space" of $A^{\prime}$ is contained in the "perpendicular space" of d. In other words, it is enough to show that $A^{\prime}x=0$ implies $d^{\prime}x=0$.

So let x be any vector in the perpendicular space of $A^{\prime}$. Then

$\sum_{i=1}^N x_i A_{i,j} = 0$ for all j. This implies $\sum_{j=1}^N \sum_{i=1}^N x_i A_{i,j} x_j = 0$,

Now we know that A is symmetric (assumption 2). Therefore, in the preceding sum, let us consider, for distinct i and j every pair of terms

$x_i A_{i,j} x_j + x_j A_{j,i} x_i = ( A_{i,j} + A_{j,i} ) x_i x_j = 2 A_{i,j} x_i x_j = 0$
because we are working in arithmetic module 2! Therefore, all the offdiagonal terms pair up and drop out.

Our sum now only involves the diagonal terms:

$\sum_{i=1}^N x_i^2 A_{i,i} = 0$
Now $A_{i,i} = 1$, because the light-switch relationship is reflexive (assumption 1), and $d_i = 1$ too, so in the sum, we can replace $A_{i,i}$ by $d_i$. Moreover, we know that $x_i^2=x_i$, because $x_i$ is either 0 or 1. Therefore, we now have $\sum_{i=1}^N x_i d_i = 0$.

Hence x is in the perpendicular space of d. This means d is in the column space of A, so a button strategy exists that turns a set of "off" lights all "on", and the same strategy will turn a set of "on" lights all "off".

## 扫雷的进一步分析

B为一个n阶矩阵,所有同主对角线相邻的位置是1(不包含主对角线),其余位置都是0,比如对于n=4,B如下
0100
1010
0101
0010

$\begin{bmatrix} B&I+B&0&0&\dots&0&0&0\\ I+B&B&I+B&0&\dots&0&0&0\\ 0&I+B&B&I+B&\dots&0&0&0\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\ 0&0&0&0&\dots&0&I+B&B \end{bmatrix}$

$f(n,x)$$n$第二类切皮雪夫多项式
$f(0,x)=1$,
$f(1,x)=2x$
$f(2,x)=4x^2 - 1$

$g(a,b)=f(m,\frac a{2b})b^m$

$\det(g(B,I+B))=(-2)^n f(n,\frac 14)$,

$f(m,\frac12\frac u{1+u})=0$,那么它为$0$,不然必然非$0$.

$\begin{bmatrix} B&I+B&0&0&\dots&0&0&0\\ I+B&B&I+B&0&\dots&0&0&0\\ 0&I+B&B&I+B&\dots&0&0&0\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\ 0&0&0&0&\dots&0&I+B&B \end{bmatrix}$

i)如果m,n都是奇数,不可逆.
ii)不然,对于$x=\cos(\frac{k\pi}{n+1}), (k=1,2,\dots,n)$

## 二维递推数列的求解

$\cos(\frac{k_1\pi}{n+1})-\cos(\frac{k_2\pi}{n+1})\ne \frac12$.

$T_{i,j}=\sqrt(\frac2n)\sin(\frac{ij\pi}{n+1}), (1\le i\le n,1\le j\le n)$.

$f(n,-B)x_1=-r_n$

$TBT=diag\{2\cos(1\times\frac{\pi}{n+1})-1,2\cos(2\times\frac{\pi}{n+1})-1,\dots,2\cos(n\times\frac{\pi}{n+1})-1\}$

$f(n,(-2\cos(\frac{h\pi}{n+1})+1)y_1(h)=-R_n(h)$,

i)首先计算$r_n$的离散正弦变换$R_n$. (如果所有d相同，我们可以发现，$R_n$的所有奇数项都是0）
ii)计算$f(n, -2\cos(\frac{h\pi}{n+1})+1), (h=1,2,\dots,n)$

iii)解出$y_1$,如果对于某个$h$,对应$f(n,-2\cos(\frac{h\pi}{n+1})+1)=0$, 而$R_h\ne 0$,那么方程无解。

iv)通过再次离散正弦变换（逆变换)计算出$x_1$

$x_k=f(k-1,-B)x_1$来计算$x_k$

$y_k(h)=f(k-1,-2\cos(\frac{h\pi}{n+1})+1)y_1(h)$

## 扫雷问题深入分析

$((2\cos(\frac{i\pi}{n+1})+1)(2\cos(\frac{j\pi}{m+1})+1)-1)X(i,j)=A(i,j)$.

$u(i,j)+t\times v(i,j)$,

$u(i,j)+t_1\times v(i,j)$$u(i,j)+t_2\times v(i,j)$都是0或1,

$\frac{2\cos(\frac{k_1\pi}{n+1})}{1+2\cos(\frac{k_1\pi}{n+1})}=2\cos(\frac{k_2\pi}{m+1})$

$(2\cos(\frac{\pi}5)+1)(2\cos(\frac{3\pi}5)+1)=1$.

$u_1+u_2+\dots+u_k=0$（其中$u_1,u_2,\dots,u_k$都是$1$的单位根，也就是有某个整数$h_i$使得$u_i^{h_i}=1$)的解。

$((2\cos(\frac{i\pi}{n+1})+1)(2\cos(\frac{j\pi}{m+1})+1)-1)$中会有一项为$0$, 其中$(i=\frac{n+1}2, j=\frac{m+1}2)$.

$(i=\frac{m+1}5, j=\frac{3(n+1)}5$$i=\frac{3(m+1)}5, j=\frac{n+1}5)$,

2014年zhouguang 将关灯问题整理成一个pdf文件 ，内容相当不错。