论文标题
解决萨特纳的猜想
Resolution to Sutner's Conjecture
论文作者
论文摘要
考虑一个在简单的图上玩的游戏$ g =（v，e）$，每个顶点由可点击的灯组成。单击任何顶点$ v $可切换$ v $及其邻居的开/关状态。一个人通过找到一系列点击来赢得游戏，以关闭所有灯。当$ g $是$ 5 \ times 5 $网格时，该游戏是从Tiger Electronics商业上获得的。萨特纳（Sutner）是第一个数学上研究这些游戏的人之一。他发现，当$ d（g）= \ text {dim}（\ text {ker}（a + i））上的字段$ gf（2）$时，其中$ a $是$ g $的邻接矩阵，为0所有初始配置均可求解。在调查$ n \ times n $网格图时，萨特纳指出$ d_ {2n+1} = 2d_ {n}+δ_{n}，δ__{n} \ in \ in \ in \ in \ {0,2 \ \} n $网格图。我们在肯定中解决了这种猜想。我们使用Sutner的结果，将$ d_n $作为环$ \ Mathbb {z} _2 [x] $的两个多项式的GCD。然后，我们应用了与$（2N+1）\ times（2n+1）$网格和$ n \ times n $网格相关的hunziker，Machiavelo和Park的身份。最后，我们使用矿石的结果，涉及两种产品的GCD。这些结果共同证明了萨特纳的猜想。然后，我们走得更远，确切显示$ n $ $δ_n$的值是0或2。
Consider a game played on a simple graph $G = (V,E)$ where each vertex consists of a clickable light. Clicking any vertex $v$ toggles the on/off state of $v$ and its neighbors. One wins the game by finding a sequence of clicks that turns off all the lights. When $G$ is a $5 \times 5$ grid, this game was commercially available from Tiger Electronics as Lights Out. Sutner was one of the first to study these games mathematically. He found that when $d(G) = \text{dim}(\text{ker}(A + I))$ over the field $GF(2)$, where $A$ is the adjacency matrix of $G$, is 0 all initial configurations are solvable. When investigating $n \times n$ grid graphs, Sutner conjectured that $d_{2n+1} = 2d_{n} + δ_{n}, δ_{n} \in \{0,2\}, δ_{2n+1} = δ_{n}$, where $d_n = d(G)$ for $G$ an $n \times n$ grid graph. We resolve this conjecture in the affirmative. We use results from Sutner that give $d_n$ as the GCD of two polynomials in the ring $\mathbb{Z}_2[x]$. We then apply identities from Hunziker, Machiavelo, and Park that relate the polynomials of $(2n+1) \times (2n+1)$ grids and $n \times n$ grids. Finally, we use a result from Ore about the GCD of two products. Together these results allow us to prove Sutner's conjecture. We then go further and show for exactly which values of $n$ $δ_n$ is 0 or 2.
