论文标题
大多数点击灯中的问题
Most Clicks Problem in Lights Out
论文作者
论文摘要
考虑一个在简单的图上玩的游戏$ g =（v，e）$，每个顶点由可点击的灯组成。单击任何顶点$ v $可切换$ v $及其邻居的开/关状态。从初始配置开始，通过找到解决方案来赢得游戏：一系列点击序列，可以关闭所有灯。当$ g $是$ 5 \ times 5 $网格时，该游戏是从Tiger Electronics商业上获得的。我们将自己限制在可解决的初始配置中，我们对此游戏提出了一个自然的问题，最单击的问题（MCP）：在$ g $上需要求解几下最糟糕的初始配置来解决？ MCP的答案已经以无效0图而闻名：每个初始配置都可以溶解。从Scherphius概括了一项技术，我们将MCP的上限给出了所有尺寸$（6K -1）\ times（6k -1）$的网格的上限。我们显示该上限给出的值正好解决了此大小的所有无效网格的MCP。我们猜想所有无效的2个网格均为$ $（6K-1）\ times（6k -1）$，这意味着我们为所有无效2平方网格求解了MCP。
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. Starting from an initial configuration of lights, one wins the game by finding a solution: 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. Restricting ourselves to solvable initial configurations, we pose a natural question about this game, the Most Clicks Problem (MCP): How many clicks does a worst-case initial configuration on $G$ require to solve? The answer to the MCP is already known for nullity 0 graphs: those on which every initial configuration is solvable. Generalizing a technique from Scherphius, we give an upper bound to the MCP for all grids of size $(6k - 1) \times (6k - 1)$. We show the value given by this upper bound exactly solves the MCP for all nullity 2 grids of this size. We conjecture that all nullity 2 grids are of size $(6k - 1) \times (6k - 1)$, which would mean we solve the MCP for all nullity 2 square grids.
