|
|
本帖最后由 Czhang271828 于 2022-2-11 15:49 编辑 昨天看走眼了, 这题和 Riemann-Roch Theorem 似乎没有太大关系. 个人解法如下:
为方便起见, 定义"解决问题"为"把所有 $1$ 变成 $0$". 可通过如下步骤判断有解的充要条件:
Step 1: 可以通过某种显然的方法将最后一横行的所有勾清除, 继而可清除倒数第二横行的勾... 以此类推, 将所有勾移动至第一横行.
方法如下:
$$
\begin{pmatrix}
0&0&1&0&1\\
0&0&1&1&1\\
0&1&1&0&1\\
0&1&\boxed0&0&\boxed1\\
0&0&1&0&1\\
\end{pmatrix}\implies\begin{pmatrix}
0&0&1&0&1\\
0&0&1&1&1\\
0&1&0&0&0\\
0&0&1&0&0\\
0&0&0&0&0\\
\end{pmatrix}.
$$
Step 2: 若存在解, 则求解步骤可交换. 从而可以在点击第一横行的"某些方块"后通过从上到下的递归完整求解. 例如点击左表的 $(1,2)$, $(1,3)$ 后可自然递归求解:
$$
\begin{pmatrix}
1&\boxed1&\boxed1&0&0\\
0&0&0&0&0\\
0&0&0&0&0\\
0&0&0&0&0\\
0&0&0&0&0\\
\end{pmatrix}\implies\begin{pmatrix}
0&1&1&1&0\\
0&\boxed1&\boxed1&\boxed0&0\\
0&0&0&0&0\\
0&0&0&0&0\\
0&0&0&0&0\\
\end{pmatrix}\implies\cdots
$$
Step 3: 看懂规律后, 我们将 Step 1 后的第一横行记作 $0$-$1$ 横向量 $v_0$ (其余横行为 $0$ 向量). 从而有解等价于存在 $0$-$1$ 横向量 $v_1$ 使得第一横行在点击 $v_1$ 对应位置后可以通过自上到下的递归求解.
Step 4: 设 $u=(a\,b\,c\,d\,e)$, 记左平移 $u^+:=(b\,c\,d\,e\,0)$, 右平移 $u^-:=(0\,a\,b\,c\,d)$. 再记 $\Delta^1 u=u^++u^-$, $\Delta^{n+1}u=\Delta(\Delta^n u)$. 此处的加法定义在有限域 $\mathbb F_2$ 上, 即 $0+0=1+1=0$, $1+0=0+1=1$. 再注意到 $^\pm$, $\Delta^k$ 与加减法可交换可结合, 从而有解等价于存在 $v_1$ 使得以下变换成立:
$$
\begin{pmatrix}v_0\\0\\0\\0\\0\end{pmatrix}\implies\begin{pmatrix}v_0+(1+\Delta^1)v_1\\ v_1\\0\\0\\0\end{pmatrix}\implies
$$
$$
\begin{pmatrix}0\\v_1+(1+\Delta^1)[v_0+(1+\Delta^1)v_1]\\v_0+(1+\Delta^1)v_1\\0\\0\end{pmatrix}\implies\cdots\implies \begin{pmatrix}0\\0\\0\\0\\0\\\end{pmatrix}.
$$
实际上, 记 $A=\begin{pmatrix}1+\Delta^1&1\\1&0\end{pmatrix}$, 则上述过程为
$$
\begin{pmatrix}v_0\\0\\0\\0\\0\end{pmatrix}\implies\begin{pmatrix}A\binom{v_1}{v_0}\\0\\0\\0\end{pmatrix}\implies\begin{pmatrix}0\\A^2\binom{v_1}{v_0}\\0\\0\end{pmatrix}\implies\cdots\implies\begin{pmatrix}0\\0\\0\\A^4\binom{v_1}{v_0}\end{pmatrix}\implies\begin{pmatrix}0\\0\\0\\0\\0\\\end{pmatrix}.
$$
即 $\begin{pmatrix}1+\Delta^1&1\\1&0\end{pmatrix}^5\begin{pmatrix}v_1\\v_0\end{pmatrix}=\begin{pmatrix}0\\\ast\end{pmatrix}$. 记一族映射 $\{a_k\}_{k\geq 0}$ 满足 $a_0=0$, $a_1=1$, $a_{k+2}=(1+\Delta^1)a_{k+1}+a_k$, 则 $\begin{pmatrix}1+\Delta^1&1\\1&0\end{pmatrix}^5=\begin{pmatrix}a_2&a_1\\a_1&a_0\end{pmatrix}^5=\begin{pmatrix}a_6&a_5\\a_5&a_4\end{pmatrix}$.
Step 5: $\begin{pmatrix}1+\Delta^1&1\\1&0\end{pmatrix}^5\begin{pmatrix}v_1\\v_0\end{pmatrix}=\begin{pmatrix}0\\\ast\end{pmatrix}$ 即 $a_6v_1=a_5v_0$, 即 $\{a_k\}_{k\geq 0}$ 作为矩阵时, $a_5 v_0$ 包含在 $a_6$ 的列向量空间中.
Step 6: 作为矩阵, $a_0=O_{5\times 5}$, $a_1=I_{5\times 5}$,
$$
\Delta^1=\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}.
$$
据递推式 $a_{k+2}=(1+\Delta^1)a_{k+1}+a_k$ 解得
$$
a_5=\begin{pmatrix}
0&0&0&0&1\\
0&0&0&1&0\\
0&0&1&0&0\\
0&1&0&0&0\\
1&0&0&0&0
\end{pmatrix}
,\quad a_6=
\begin{pmatrix}
0&1&1&0&1\\
1&1&1&0&0\\
1&1&0&1&1\\
0&0&1&1&1\\
1&0&1&1&0\\
\end{pmatrix}.
$$
从而 $v_0$ 应属于 $a_5^{-1}a_6$ 的列空间, 即
$$
\mathrm{span}\left\{
\begin{pmatrix}1\\0\\0\\0\\1\end{pmatrix},
\begin{pmatrix}0\\1\\0\\1\\0\end{pmatrix},
\begin{pmatrix}0\\0\\1\\1\\1\end{pmatrix}
\right\}.
$$
从而所有可解情形对应的 $v_0$ 为向量 $\begin{pmatrix}1\\0\\0\\0\\1\end{pmatrix},
\begin{pmatrix}0\\1\\0\\1\\0\end{pmatrix},
\begin{pmatrix}0\\0\\1\\1\\1\end{pmatrix}$ 在 $\mathbb F_2$ 上的线性组合, 共计 $8$ 类.
Step 7: 实际操作如下 (以一楼题目为例, 目标是关掉所有灯):
1. 经 Step 1 得 $\begin{pmatrix}
1&0&0&0&1\\
0&0&0&0&0\\
0&0&0&0&0\\
0&0&0&0&0\\
0&0&0&0&0\\
\end{pmatrix}$.
2. 由 $a_5v_0=a_6v_1$, 得
$$
\begin{pmatrix}
1\\0\\0\\0\\1
\end{pmatrix}=\begin{pmatrix}
0&1&1&0&1\\
1&1&1&0&0\\
1&1&0&1&1\\
0&0&1&1&1\\
1&0&1&1&0\\
\end{pmatrix} v_1
$$
观察得 $a_6$ 矩阵中前两列相加即为 $a_5v_0$, 从而取 $v_1=(1\,1\,0\,0\,0)$.
3. 在$\begin{pmatrix}
1&0&0&0&1\\
0&0&0&0&0\\
0&0&0&0&0\\
0&0&0&0&0\\
0&0&0&0&0\\
\end{pmatrix}$ 中点击 $(1,1)$, $(1,2)$ 中元素, 再从上到下地消元即可.
判断与解决 $n\times n$ 情形的计算步骤是 $n^3+O(n^2)$, 其中所有加减乘除运算都是 $\mathbb F_2^n$ 上的, 因此跑起来不慢. |
|
Czhang271828
发表于 2022-2-10 15:22
