|
|
Last edited by Czhang271828 at 2023-3-4 14:45:00其实这个问题写过的, 见此帖. 一般情况的解法无非常微分那类"特解"+"通解"的形式, 也就是其中一种解法+把零变成零的方法.
对 $n\times m$ 网格, 可以用逐行消掉第 $1$ 横行至第 $n-1$ 横行, 进而所有黑块在最后一横行. 注意到在一个空白的网格中, "点击第一行的某个方块+应用上述归纳消去法"的总体效果是在最后一行凭空创造若干黑块, 换言之, "点击第一行的一个方块"等价于"改变最后一行的若干方块".
由于所有步骤可交换, 我们可以用矩阵反推最后一行黑块所对应的"第一行应做的变换". 对 $5\times 5$ 的情形, 解空间和零空间是显然的.
当然还有个很显然的结论, 如果把灯对应成图上的点, 边对应点亮关系, 那么无向图一定可以从全亮变成全暗.
回答原问题, 即 $3\times 3$ 的网格中只有 $(1,1)$ 是绿的, 求变全白的最少步数?
- 通过点击第一行+递归消去法, 找到"凭空创造最后一行绿块"的所有方法: 这里是
\[
(1,1)\mapsto (3,2)+(3,3),\quad (1,2)\mapsto (3,1)+(3,2)+(3,3),\quad (1,3)\mapsto (3,1)+(3,2).
\]
由于 $\mathbb F_2$ 上有满秩矩阵 $\det\begin{pmatrix}1&1&0\\1&1&1\\0&1&1\end{pmatrix}=1$, 从而把"点击第一行方法"映至"最后一行绿块改变"的 $\mathbb F_2$-线性映射是双射. 进而任意初始状态的绿块都可以被消除, 这也蕴含没有非平凡的"通解". - 找到消去 $(1,1)$ 块的"特解", 在"通解"平凡时也就是唯一解了, 题中 $5$ 不但是最少步数, 而且是唯一的步数(根据各步骤可交换性和对称性, 我们不妨约定每个块至多点一次).
对 $5\times 5$ 情形, 把"点击第一行方法"映至"最后一行绿块改变"的 $\mathbb F_2$-线性映射不是满秩的, 所以会有无解的情况. 一个值得研究的问题是 $n\times n$ 在何种情况下一定有解? 按照传统意义下的算法, 这个复杂度是 $\mathcal O(n^{2.3})$ 左右. |
|
kuing
Posted at 2023-3-3 23:00:38
Czhang271828
Posted at 2023-3-4 14:19:23
