灯光©
如果您只对解决灯光游戏问题感兴趣，请跳过下面的游戏提示。
在开始之前，让我们介绍一些数学术语。
数学语言
我们也将借机会练习数学的形式体系并且将声明整合进
- 假设（提出的陈述作为进一步调查的起点）
- 定义（解释一个词或短语的意思）
- 定理 （大胆声明）
- 引理 （次要声明）
- 证明 （毫无疑问地说明定理和引理是正确的声明。符号 □ 将意味着证明的结束）
- 推论 （直接由定理或引理得到的声明）
探索一个主题的一个好方法是问自己一些简单的问题并尝试回答它们。现在我们就来这样做。你可以将此页面视为进行研究的手册，尤其是研究对称性的部分。在此过程中，我们将找到有关如何玩游戏的提示。
点击的顺序是否重要？
不。灯光的状态只取决于点击灯本身和相邻的灯的次数，不取决于点击的顺序。如果点击灯本身和相邻的灯的总数是偶数，那么灯的状态不会改变，如果是奇数次那么状态就会改变，仍然与点击顺序无关。
例子：选两个不同的相邻灯光，比如A和B。以A，B，B，A的顺序点击它们。结果会如何?↠ 不会有变化，因为B没有影响，A也没有。
现在调换前两次点击的顺序并且以B, A, B, A的顺序点击它们。结果会如何?↠ 仍然没有变化。前两次点击的顺序并不重要。如果我们以任意顺序分别点击两次两个按钮，情况仍然一样。点击的顺序并不重要。
如果点击的顺序并不重要，那么如何减少长序列的点击次数呢?
以下是其中一种减少点击次数的方法。
为了解决问题，每个人可以记录每个灯被点击的次数。之后可以将每个灯上的偶数的点击量记为0，并将奇数记为1。新的顺序与之前等效并且也是一种解答。
定义：如果每个灯最多开一次，那么这组点击的序列会被称为简化后的。以上的过程叫做简化。
简化后的点击序列长度最长是多少？
- 一个序列只能有与灯的数量相同的点击量因为在一个被简化的序列中每个灯最多只能被点击一次。因此，如果格子总的高度为 h 宽度为 w 就有 h×w个灯，可以减少的序列最多有 h×w 次点击。
如果移动的顺序并不重要，那么如何才能对一个解决方案进行完整的搜索（蛮力搜索），即一个能打开所有灯的点击序列？
因为点击的顺序并不重要，只要知道每个灯是否在解决方案中被点击就足够了。因此，尝试单击所有灯光的所有组合就足以进行完整的蛮力搜索。
如果题板中有 h×w 个灯，那么它们就有 2h×w 个组合（每个灯有 2 个选项，无论它是否在该组合中被点击）。 这样的蛮力搜索将花费太长时间。 但是，如果“提示”已打开（在比赛中不可用），则可以简单地一一点击所有灯，并检查此点击是否让你更接近解决方案。 如果是，则留下它，如果不是，就再次单击它。
以下的问题可进一步地简化点击的序列。
如果所有灯都是亮的并且每个灯都只被点击一次，将会发生什么?
-
引理：
如果在一个矩形所有灯都是亮的并且每个灯都只被点了一次，这之后角落的灯将被关掉（O），所有其它在边缘的灯将变被打开（#）并且所有剩下的灯将被关掉，就如这个4×4的题板所示。
# # # # O # # O
# # # # # O O #
# # # # # O O #
# # # # O # # O
before after
证明：
首先，每个灯都被点击了所以都被开或关了一次。当其相邻的灯被点击时，一个灯也会被开启或关闭。
所以，如果相邻的灯的数量是偶数，那么这个灯将被开关偶数次，所以总的来说一共是奇数次。所以它将扔保持关闭状态，如果它最初是开启的。
相似地，如果相邻方块的数量是偶数，那么灯将被开启奇数次，所以总共将被开启偶数次。所以，如果它最初是亮的，它将仍然是亮的。
通过数每个灯相邻的灯的个数，我们可以得到引理的声明 □
在简化后的点击序列的开头和结尾，所有的灯都是亮的吗？我们将这样的序列称为一个循环。
- 从所有灯都开启时开始的循环
- 有两种不同的简化序列，两种都可以将所有灯关闭
- 把两个序列合并之后也能使灯在开始和结束时都为开启状态的序列后
- 简化所得序列以获得一个循环。这个简化的循环包括点击因为两个结合过后的序列都不同，所以在一个序列中至少有一次点击但这并不在另外的原本的序列中。化简后并别结合的序列将有这种点击。
如果每个灯都被点击了偶数次那么简化（此前已释）在每个灯上只有0次点击，并且不惊讶的是，所有的灯都保持为开启状态。但是有没有简化的点击序列在开始和结束时，灯都是亮着的呢？
定义：如果所有灯都在以序列点击前后有同样的状态，至少有一次点击的简化后的序列被称为循环
我们将先以所有灯都开启开始并且以所有灯都开启结束，以找到循环。这样的循环将不会同时改变所有其它的初始状态，换句话说，如果开始时题板上有些灯是开启的有些灯是关闭的，而且我们运行了这个循环，那些相同的灯还会有相同的状态。你可以证明吗？
一种可能性是尝试找到
哪种题板尺寸是有可能的？对于一个具体的题板尺寸，我们可以建立并研究一个线性代数等式来解答这个问题。在以下的参考源中可获取更多相关信息。
如何找到4 X 4题板的循环？
-
我们从所有灯都打开 (#) 开始，然后准确地单击每个灯一次。可得
O # # O
# O O #
# O O #
O # # O
因为我们正在寻找一个循环，即在所有灯都打开的情况下开始和结束，我们尝试单击所有关闭的灯（显示为 O）一次，这不仅会打开它们，还会使所有其他灯保持打开状态。 请自行验证。
提醒：首先我们点击所有灯然后在把对角线上的灯再点一次。所以我们把对角线上的灯点了两次。通过分解整个序列，所有在对角线上被点了两次的灯会烧毁且只有在板上标为＃的灯上的点击会被保存。所以，我们以所有灯打开为开始且以所有灯打开为结束。所以在板上灯的8个点击形成了一个循环！耶，我们找到了一个循环！ 🥳
请尽量尝试并且说服自己点击上方8个标为 # 的灯不会改变 4 X 4题板上的灯。从所有灯都开启时开始将会非常明显。
如何用循环进一步简化序列？
如果已知一个循环，那么这可能对于进一步缩短序列有用。
引理：如果已知一个循环有 c 次点击并且有一个序列包含 n 次点击，那么用 c−n 次并不在循环内的点击替换这些点击将会得到等效序列。
证明：这个证明是推定性的，换句话说，它展示了如何推出这样的序列。
如果我们把序列加在一个循环后，那么结合后的新序列将与之前等效，因为我们增加了一个循环。在结合后的序列中n次点击出现了两次，一次在原本序列中另一次在循环中。 通过化简，换句话说，删除这些双击，新的序列仍然等效（因为化简 产生了等效序列）并且现在没有 n 次点击，反而有 c−n 次属于循环的点击。 □
推论：如果 c - n < n那么新的序列会更短。这当且仅当 n > c/2 时成立 用文字：如果一个序列与一个序列有超半数相同的点击，那么这个序列可以用循环来缩短。
例子：在一个4×4的板子上放置13个灯(用铅笔在纸上画)，最开始所有灯都被打开，然后分别点击13个灯并画出结果图(为什么举的例子是13而不是…比如12？之后我们会解释 :-) ) 现在检查这13次点击哪个属于循环并做出一列循环点击被其他在循环内的点击代替的新的点击序列(用铅笔在纸上写)。还是以所有灯打开为开始并使用这一更短的点击序列。
结果是什么？
你的结论应该是这次更短的结果与上次的相同。
4×4的题板上缩短的点击序列的最长长度是多少？
-
定理：
4×4题板上的点击序列可以被最大程度地简化成12次点击
证明：我们知道 4 X 4题板上的化简序列只有 4 X 4=16次点击 我们同时发现如果一个序列与一个循环有超半数相同的点击，那么它可以被缩短。 我们知道 4X4 题板上的一个包含8次点击的循环。所以一个序列最多可以有 16 - 8=8次不属于循环的点击 所以，一个被简化并缩短的序列最多有
8 （不属于循环的点击）
+ 8/2 半数来自循环的点击）
= 12 次点击
在一个 4 X 4的题板上。 □
所有可能遇到的在 4 X 4题板上打开所有灯的问题可以在最多12次点击中被解决。
阐明：该定理没有说明是否存在不能用循环缩短长度为 12 的序列。也许最大长度是 12、10 或 8。该定理只说它不能超过 12 次点击。
根据上述结论，什么可能是 4×4 问题的例子，需要最多的点击次数才能打开所有灯？
我们点击所有不在循环中的灯，所以对角线上的所有8个灯。然后我们从循环中挑选4个灯，例如，顺时针方向每边一个。用©表示点击，我们做了以下12次点击：
© · © ©
© © © ·
· © © ©
© © · ©
题板上的结果是
# O O #
O # # O
O # # O
# O O #
这个12次点击的序列现在是不能再缩短的最大长度吗？
不是，这4次点击
· © · ·
© · · ·
· · · ©
· · © · 有相同的结果：
# O O #
O # # O
O # # O
# O O #
这意味着什么？
这意味着我们有了一个 12+4=16 次点击的新循环，耶！🥳 如果我们放弃双击(© + © = ·)，这个新的 12 次点击循环仍然存在：
© · © © · © · · © © © ©
© © © · + © · · · = · © © ·
· © © © · · · © · © © ·
© © · © · · © · © © © ©
请验证这是一个循环。
当我们把12次点击的循环和8次点击的循环相加，并把它缩短，会产生什么？
两个循环之和一定是一个循环，即不改变题板：
© © © © · © © · © · · ©
· © © · + © · · © = © © © ©
· © © · © · · © © © © ©
© © © © · © © · © · · ©
给出了 12 次点击循环的 90°旋转版本，这是我们新的第 3 个循环。 请确认这也是一个循环。
这对于 4×4 题板上的点击序列的最大长度意味着什么？
序列
© · © © · · © ·
© · · · and © © © ·
· · · © · © © ©
© © · © · © · ·
每个都有 8 次点击。
能否用3个循环来缩短它们？
每一个都与 8 次点击循环正好重叠 4 次点击，并与每个 12 次点击循环重叠正好 6 次点击。 请验证这 6 条说明。 它们不会与每个循环重叠超过一半的循环点击次数。 因此，这些序列不能通过这 3 个周期缩短，但只需再单击一次即可缩短它们。
我们提出这个未经证实的猜想：
假设：在 4×4 题板上不能缩短一个周期的点击序列的最大长度为 8。
欢迎你来证明这一点。首先，我们必须证明没有其他独立的循环。
在下文中，我们将研究 5×5 题板并研究更多的对称性。
5 X 5的题板会怎样？你能在其中找到一个循环吗？
- 从都是亮着的灯开始
- 每个灯点击一次可得
O # # # O # O O O # # O O O # # O O O # O # # # O - 点击一次对角线上所有的灯，同时也点一次中间的灯。结果将会是所有灯都亮了。
- 通过放弃所有对角线上的双击来简化序列，会留下 25 - 9=16次以©展示的点击：
· © © © · © · © · © © © · © © (1) © · © · © · © © © · - 恭喜，我们找到了一个循环，耶！🥳
与 4 X 4的题板相似，我们
请尽量尝试并且说服自己点击上方16个标为© 的灯不会改变5×5 题板上的灯。从所有灯都开启时开始将会非常明显。
在 5×5 题板上的缩短点击序列长度的上限是多少？
-
定理：
5×5 题板上的一系列点击不能超过 17 次。
证明：我们知道 5×5 题板上的化简序列只能有 5×5=25 次点击 我们知道 5×5 题板上的一个包含16次点击的循环。所以一个序列最多可以有 25−16=9 次不属于循环的点击 我们同时发现如果一个序列与一个循环有超半数相同的点击，那么它可以被缩短。 所以，一个被简化并缩短的序列最多有：
9 （不属于循环的点击）
+ 16/2 （半数来自循环的点击）
= 17 次点击
在一个 5X5的题板上。□
如果一个在 5X5 题板上打开所有灯的问题有解答，其可以在最多 17 次点击中被解决。
说明：这是否意味着有 17 次点击的序列无法缩短？
回答：不，到目前为止我们不知道。
对称性在这个游戏中起什么作用？
因为棋盘是长方形的，开/关灯的图案可能是90°或180°的旋转对称，也可能是沿水平或垂直对称线的镜像对称。如果棋盘是一个正方形，它也可能沿着一条对角线甚至两条对角线有镜像对称性。
在下文中，我们的想法是，解决方案由一些具有这种对称性的点击和其他不具有这种对称性的点击组成。
我们如何才能取得进展？
我们需要灵感，我们从玩游戏和随机点击灯光中获得灵感，直到我们得到一个看起来很奇怪或对称的棋盘。 然后我们想知道点击的顺序是否也很特殊。
我们可能会遇到这样的题板：
O O O O O
# O # O #
O O # O O (2)
# O # O #
O O O O O
并且忘记了我们是如何到达它的。 这很容易通过选择“提示”并单击每个位置来查找。 如果“提示：您最多可以赢得 XX 次点击”中显示的数字减少了，我们会记下该位置，如果没有，我们会再次单击它。 我们找到了这个解决方案，其中 © 表示点击：
· · · · ·
© © © © ©
· · © · · (3)
· © · © ·
© · © · ©
现在我们应该真的很惊讶并且很好奇！
为什么？
因为题板（2）有一个镜像对称，中间的水平线是对称线，但解决方案没有这个对称性。在数学中，一个对称的问题有一个非对称的解决方案，这是很罕见的。
现在怎么办？
我们应该通过提取（3）的对称部分和非对称部分来研究这个问题。
因此，我们将 (3) 写为对称部分和非对称部分的总和：
· · · · · · · · · · · · · · ·
© © © © © · © · © · © · © · ©
· · © · · = · · © · · + · · · · ·
· © · © · · © · © · · · · · ·
© · © · © · · · · · © · © · ©
就像寻宝者在寻找宝石一样，我们在数学中也在寻找独特的物品。 上述分解不是唯一的。 有很多方法可以将非对称部分写成一个对称部分和另一个非对称部分之和。
有没有独特的分割？
我们可以通过要求非对称点击仅在对称线的一侧来使其独一无二。
我们使用© + © = ·，因此现在写为
· · · · · · · · · · · · · · · · · · · ·
© © © © © · © · © · © · © · © · · · · ·
· · © · · = · · © · · + · · · · · + · · · · ·
· © · © · · © · © · © · © · © © · © · ©
© · © · © · · · · · · · · · · © · © · ©
· · · · · · · · · ·
© © © © © · · · · ·
= · · © · · + · · · · ·
© © © © © © · © · ©
· · · · · © · © · ©
知道我们是在做什么，我们现在想知道关于它的一切。
因为原来的题板是对称的，对称的部分必须组成一个对称的题板，所以非对称的序列也必须组成一个对称的题板。
它是什么？
· · · · · O O O O O
· · · · · O O O O O
· · · · · (4) generates the board # O # O # (5)
© · © · © O O O O O
© · © · © O O O O O
请检查一下！
我们将看到，很少有非对称解能产生一个对称的棋盘，并且所有的点击都在对称线的一边。
如果一个人绕过题板 (5) 并从另一侧看它和解决方案 (4) 会怎么样？
题板看起来是一样的（因为它有180°的对称性），但解决方案变成了
© · © · ©
© · © · ©
· · · · · (6)
· · · · ·
· · · · ·
所以（6）是另一个非对称序列，产生了相同的对称板（5）。这是个意外还是一般情况下都是这样？
这是个一般声明：
如果一个对称问题（这里是（5），具有180°的对称性）由一个非对称序列（这里是（4））产生，那么对这个序列进行对称操作（这里是180°旋转）会产生一个新的非对称序列（这里是（6）），产生相同的题板（这里是（5））。
当一个人同时执行两个非对称序列时会发生什么？
在第一个序列 (4) 之后，三个灯关闭（在板 (5) 中），在第二个序列 (6) 之后，三个灯再次切换，现在打开。 这意味着 (4) + (6)
© · © · ©
© · © · ©
· · · · · (7)
© · © · ©
© · © · ©
是一个 12 次点击循环！ 万岁！！🥳 请通过这 12 次点击来验证这一点。
这个新周期可以用来做什么？
与其他 16 次单击循环一样，这可用于缩短单击序列。
可以用 12 次点击周期缩短 16 次点击周期吗？ 结果必须是一个循环，因为循环 + 循环 = 循环。
执行两个循环给出（因为 © + © = · ）
· © © © · © · © · © © © · © ©
© · © · © © · © · © · · · · ·
© © · © © + · · · · · = © © · © © (8)
© · © · © © · © · © · · · · ·
· © © © · © · © · © © © · © ©
这必须是一个循环，是的，它只是循环（7）旋转了 90°。
16 次点击循环也是对称问题的两个非对称解的总和吗？
我们有 2 种方法可以将 16 次点击循环写成总和：
· © © © · · · · · · · © © © ·
© · © · © © · · · · · · © · ©
© © · © © = © © · · · + · · · © © (9)
© · © · © © · © · · · · · · ©
· © © © · · © © © · · · · · ·
· © © © · · · · · · · © © © ·
© · © · © © · · · © · · © · ·
© © · © © = © © · © © + · · · · · (10)
© · © · © © · · · © · · © · ·
· © © © · · · · · · · © © © ·
(9)右边的两个序列中的每一个都是非对称序列，导致对称题板的出现
# O O O O
O O O O O
O O O O O (11)
O O O O O
O O O O #
(10)右边的两个序列中的每一个都是非对称序列，导致对称题板的出现
# O O O #
O O O O O
O O O O O (12)
O O O O O
# O O O #
因此，16 次点击循环是对称问题的两个非对称解的总和，即使是两种方式。
如果想尽量减少需要记忆的序列数量，那么只需记住
· · · · ·
© · · · ·
© © · · · (13)
© · © · ·
· © © © ·
因为(9)右边的另一个序列有同样的效果，(10)右边的序列只是(13)和(13)的90°旋转的总和。
这对解决对称题板有什么帮助？
如果对于5×5题板来说，序列（4）、（13）和它们的90°旋转是产生镜像对称题板的唯一非对称序列（除了产生其他非对称序列的对称点击），那么要解决一个镜像对称题板，只需要执行对称棋步，直到所有的灯都亮起，或者直到到达题板（5）或（11）之一（或它们的90°旋转），然后简单地执行序列（4）或（13）（或它们的90°旋转）。
换句话说，要解决一个镜像对称的5x5题板，人们只需要尝试对称的点击组合，而这些组合需要较少的这种对称的点击，因此会产生较小的搜索树。
5×5题板上缩短的点击序列的最大长度是多少？
我们不回答这个问题，但我们有两个建议。
假设：对于一个5×5的题板来说，没有其他的循环不是由12、12和16次点击的3个循环组合而成的。
假设：在 5×5 题板上的缩短点击序列的最大长度为 13。
我们把它留给你去思考一个证明或反例，即另一个独立的循环或一个超过13次点击的序列，它不能用有12次、12次和16次点击的3个循环（7）、（8）和（1）缩短。第一个假设可以用线性代数来检查（见下文），但如果能有一个简单的证明或一个不同的周期就更好了。一个不能用 3 个循环减少的 13 次点击的序列示例是
© · © · ©
· © · © ·
© · © · ©
· © · © ·
© · © · ©
祝你在（重新）搜索和证明中获得乐趣!
是否可以达到题板上所有的 ON/OFF 灯模式？
h×w 灯有 2h×w 模式的 ON/OFF 灯。 正如我们之前发现的，还有 2h×w 个可能的点击序列。
但也有序列产生相同的棋盘图案，即任意序列和这个序列+循环。 因此，我们有比可达板模式更多的序列，因此必须存在无法到达的板模式。
在数学中有这样的情况。 如果每个点击序列都会产生不同的模式，那么序列到模式的映射将被称为单射。 如果每个模式都是一些点击序列的结果，那么序列到模式的映射将被称为满射。 因此，我们的点击模式序列图是非单射和非满射的。
玩游戏的提示
准备练习
为了准备在比赛中玩游戏，从一个所有灯都亮着的题板开始是很有帮助的。 为了得到这个题板，将“最初点击”和“紫灯”的数量降低到 0，并增加题板的大小。 然后在直接相邻或对角相邻上单击 2 次，并记住生成的模式，以便在游戏中出现它们时识别它们。 在角落、边缘和中间进行此类尝试，因为图案也取决于位置。
一种不同的做法是，在一个5×5的题板上，所有的灯都打开，然后点击那些相对于对角线或中线对称的灯，或者是相互旋转90°或180°的灯，看看你能得到哪种对称的图案。
如果附近有一小组灯不亮，应该首先尝试什么？
在这种情况下，应首先尝试在此类小组灯的中心移动，因为单击此类小组灯的边缘只会关闭更多的灯，并扩大关闭的灯组。 如果不成功，则必须点击更远的更多灯，最终不得不在整个题板上进行点击。
如果题板图案具有对称性怎么办？
最初的题板可能是相对于一个或两个对角线或相对于水平和/或垂直的对称线的镜像对称。其他的对称性可能是90°或180°的旋转对称性。在 "对称性在这个游戏中起什么作用？"一节中，我们得出了以下策略：
One performs groups of symmetric clicks which preserve the symmetry until either all lights are ON, or when having a board of size 5×5 until one reaches one of these boards:
O O O O O # O O O O # O O O #
O O O O O O O O O O O O O O O
# O # O # (5) or O O O O O (11) or O O O O O (12)
O O O O O O O O O O O O O O O
O O O O O O O O O # # O O O #
（或它们的 90°旋转），然后简单地执行序列：
· · · · · · · · · · · © © © ·
· · · · · © · · · · © · © · ©
· · · · · (4) resp © © · · · (13) resp © © · © © (1)
© · © · © © · © · · © · © · ©
© · © · © · © © © · · © © © ·
（分别旋转 90°）。
“玩对称”是什么意思？
如果对称线上的任何灯关闭，则需要单击该灯本身。 原因：如果一个人不会单击它而只单击一个相邻的灯，那么另一个与对称线对称的相邻灯应该 也可以单击，然后对称线上的灯将切换两次并保持关闭。
如果对称线上的任何灯关闭，则需要单击该灯本身。 原因：如果一个人不会单击它而只单击一个相邻的灯，那么另一个与对称线对称的相邻灯应该 也可以单击，然后对称线上的灯将切换两次并保持关闭。
如果位置相对于两条对称线（两条对角线或水平和垂直中间线）对称，则上述规则适用于两条线。 需要单击这些线上的任何关闭的灯，并且不得 单击这些对角线上的任何打开的灯以使所有灯都打开并获得对称解决方案。
如果题板不是镜像对称的，而是旋转对称的，那么就可以用相同的旋转对称性进行点击分组来保持这种对称性。
不管对称性是什么，当你点击一个灯时，也要点击对称性相关的灯。换句话说，如果是90°对称（4倍旋转对称），那么也要点击其他3个灯，如果是180°对称（2倍旋转对称），那么也要点击其他一个灯。如果是镜像对称，那么也要点击镜像对称的灯。如果一个灯是它自己的对称灯，那么就只点击它一次。需要点击一次的灯的例子是在任何对称下的中心灯，或在对角线镜像对称下的对角线上的灯，或在通过中心的水平线或垂直线上的灯，如果该线是对称线的话。
如果在点击一个灯和它所有的对称灯后，对称性增加了（例如2个镜像对称，而不是一个镜像对称），那么从现在开始使用增加的对称性。
如果题板图案没有对称性怎么办？
如果题板没有对称性，那么我们可以试着做一些点击，使更多的灯打开而不是关闭。然后，我们可以做一些动作，让关灯的位置更靠近。迟早会产生一个对称的位置，然后继续进行对称的点击。
最后三个问题与更普遍的情况有关。
对于寻找导致某种给定题板模式的点击序列，一般的解决策略是什么？
Wikipedia 上给出了这个谜题的历史和一般解决方案的概要。Wolfram MathWorld 上给出了另一个更多的数学描述和更多的参考资料。你可能想检查我们的发现是否包含在这些出版物中。
是否可以将某些灯的每个最初位置打开而其余的灯都关闭，以更改为所有灯都打开？ 如果不是，怎么知道？ 如何找出给定尺寸的题板是否有循环，如果存在，找到循环。
这些问题可以通过制定和研究线性代数方程组来回答。 可以在上面给出的参考资料中阅读更多相关信息。
如果有紫灯，以上理论是否成立？
紫灯可以改变所有事情。在有紫灯的情况下需要坚持以上每个声明是否仍然成立，或者改变声明以使它们仍然成立。线性代数将会是个能概括有紫灯的题板的，灵活的并且足够普遍的方法。
关注或订阅更新：