另一个有趣的小问题

· · 算法·理论

在 10x10 网格内有 38 个格子被标记，使得：

证明：恰好有 3 个 2x2 的小正方形内全都不被标记。

更一般地，如果 nxm 网格中满足条件地标记了 k 格，结论应该如何变化？

.

.

.

.

.

.

.

.

.

.

如果没有想法，可以看一看下面这个图例。图例中 x 代表被标记的格，. 则反之，, 处指示了 3 个没有标记的正方形。

......,,..
.xxxxx,,x.
.x.x.,,xx.
...xx,,.x.
.xxx,,x.x.
.x..,,xxx.
.xx.x..x..
.x..xxxxx.
.xxxx.x.x.
..........

.

.

.

.

.

.

.

.

.

.

注：以下证明来自我的同学。

可以发现，标记格形成了一棵树。下面证明这一点。

假设标记格形成的图中有环。取这个环的一个拐角，不妨设其上方和右方也被标记。如果右上方有标记，就与每个 2x2 小正方形不都被标记矛盾；如果右上方没有标记，这个环就会将它与最外圈隔开。因此无论如何都会产生矛盾。

接下来还可以发现，每个叶子处都形如：

...
.x.
?x?

下面证明这一点。不妨设它仅有下方的格被标记，那么左、上和右边的格不被标记。如果其左上的格被标记了，那么树上连接这两个点的路径就会把左边的格和上面的格分割开，因此左上没有标记。右上同理。

那么，如果将一个叶子处的标记移除，恰好会增加两个全部不被标记的2x2 小正方形。而移除这个标记后，条件仍然都成立，因此可以继续移除。

这样一直操作下去，在剩余至少两个标记格时会增加两个，而移除最后一个标记格时会增加四个。因此无标记正方形一共增加了 37x2+4=78 个。而最终的无标记图一共有 81 个无标记正方形，因此初始时有 3 个。

对于一般的情形，仿照上述过程，答案就是 (n-1)(m-1)-(2k+2)，k=0 的特殊情况为 (n-1)(m-1)。

实际上，本题来源于 Steam上的《14种扫雷变体》 里的一种结合规则。

游戏里有 7 种全局限制变体，其中一种为 [Q] 无方：每个 2x2 的小正方形内都至少有一个雷，另一种为 [O] 外部：空格四连通，雷与边界四连通。在后期解锁的 [+'] 章节中出现了 [O][Q] 规则，此规则的 8x8 棋盘的雷数为 26。将空白格改称为标记格，并在最外面加上一圈非标记格，限制就和上述题目一致了。

前天官方群里正好聊到了这个规则，然后某大佬说：

塞德莎 2022/12/9 18:42:55
聊下去就要引出来一个非常阴间的东西

塞德莎 2022/12/9 18:44:56
数学能力强的可以去证明一下8X8-26雷的情况下，OQ的2X2雷区域数目最多是多少个

塞德莎 2022/12/9 18:45:42
如果能成功得到结论，你就入门了纸笔谜题里非常全局的一个概念——penalty

塞德莎 2022/12/9 18:48:08
最早测试版OQ 8x8 生成谜题的时候就出现了生成题目卡死的情况，后来是结合了这个penalty的结论才顺利生成了100关

并抛出了上述结论。

这里提到的 penalty 理论的可以在 https://chaoticiak.github.io/penaltydynasty.html 上了解。由于我不是很看得懂英文就不继续扯了。

《14种扫雷变体》真好玩，我推荐大家都来玩一玩。我已经浪费了上百小时了，还想继续玩。如果你想先云一云，我写了一份极短的规则介绍。

为了一碟醋（推荐游戏）包了一碗饺子（搞了个题），确信（

Update on 2022/12/15:

结合别人的一些提示我想到了一个更简单的证明。

考虑标记格形成的图形。由于每个 2x2 的小正方形内都不全被标记，因此每个标记格的四个顶点都在边界上。那么，如果把每个格点都当做顶点，标记格组成的图形的内角和即为 38x360°。

再由于非标记格是连通的，标记格就不会出现一个环把内外分割开的情况，因此内角和公式 (n-2)x180°适用。那么这是一个 78 边形，即标记格经过 78 个格点。

显然，除掉这些格点和大正方形的边界点，剩下的格点就是一个无标记正方形的中心，且显然这是一个一一对应。那么就有 (10-1)x(10-1)-78=3 个无标记正方形。