← 返回子刊列表

关于 $m \times n$ 扫雷网格中最大数字和的推广证明

作者：lixiang90, gemini 3 pro(Canvas)

发布时间：12/10/2025, 3:36:57 PM

查看使用的 Prompt

使用图中的方法，推广到m乘n的情况，从而证明m乘n的扫雷的最大数字和为3mn-2m-2n+2-min(m,n). 把这个证明写成论文，以markdown格式撰写，不要使用完整的latex文档（附图来自zhautykov 2020 p6，见：https://izho.kz/wp-content/uploads/2020/01/day_2_solutions_eng.pdf）

关于 m×nm \times n 扫雷网格中最大数字和的推广证明

摘要

本文旨在推广经典的 n×nn \times n 扫雷染色问题结论。原问题证明了在 n×nn \times n 的网格中，黑白染色后白色方格上的数字之和的最大值为 3n2−5n+23n^2 - 5n + 2。本文利用顶点赋权法（Vertex Weighting Method）和路径引理（Path Lemma），将该结论推广至任意 m×nm \times n 的矩形网格，并证明其最大数字和为 3mn−2m−2n+2−min⁡(m,n)3mn - 2m - 2n + 2 - \min(m, n)。

1. 问题定义

给定一个 m×nm \times n 的网格（m,n≥2m, n \ge 2），其中一些方格被染成黑色，其余为白色。在每个白色方格中写入一个数字，该数字等于与其至少共享一个顶点的黑色方格的数量。求所有白色方格中数字之和 SS 的最大可能值。

2. 证明方法：顶点赋权法

类似于原题的解法，直接计算方格内的数字之和较为困难。我们通过计算“异色方格对”在网格顶点上的贡献来转换问题。

2.1 贡献的转换

总和 SS 等于所有“共享至少一个顶点的黑白方格对”的数量。这类方格对分为两种：

  1. 共边对（Sharing a side）： 两个方格共享一条边（及其两个端点）。
  2. 共点对（Sharing a vertex）： 两个方格仅共享一个顶点。

我们将贡献分配到网格的顶点（即方格的角点）上：

  • 初始时，所有顶点的值设为 0。
  • 对于每一个共点对，将其唯一的公共顶点的值加 1。
  • 对于每一个共边对，将其两个公共顶点的值各加 1/2。

显然，所有顶点上的最终数值之和等于 SS。

2.2 顶点的分类与最大势能

对于 m×nm \times n 的网格，顶点总数为 (m+1)(n+1)(m+1)(n+1)。我们将顶点分为三类，并分析其在任意染色下能达到的最大值：

  1. 内部顶点（Internal Vertices）：
    • 数量：(m−1)(n−1)(m-1)(n-1)。
    • 连接 4 个方格。
    • 最大值条件： 当且仅当该顶点连接 2 个黑色方格和 2 个白色方格，且同色方格共边时（即形成黑-黑、白-白并排），该顶点获得最大值。
    • 计算：2个共边对贡献 2×0.5=12 \times 0.5 = 1，2个共点对（对角线方向）贡献 2×1=22 \times 1 = 2。
    • 最大值：3。
  2. 边界顶点（Border Vertices，不含角点）：
    • 数量：2(m−1)+2(n−1)2(m-1) + 2(n-1)。
    • 连接 2 个方格。
    • 最大值条件： 两个方格颜色不同。
    • 计算：1个共边对贡献 0.50.5。
    • 最大值：1/2。
  3. 角点（Corner Vertices）：
    • 数量：4。
    • 连接 1 个方格。
    • 无法形成黑白对。
    • 最大值：0。

2.3 理论上限（Raw Upper Bound）

如果不考虑全局染色的几何约束，仅将所有顶点的最大值相加，我们可以得到一个理论上限 SboundS_{bound}：

Sbound=3×(内部顶点数)+12×(边界顶点数)+0=3(m−1)(n−1)+12(2(m−1)+2(n−1))=3(mn−m−n+1)+(m−1+n−1)=3mn−3m−3n+3+m+n−2=3mn−2m−2n+1\begin{aligned} S_{bound} &= 3 \times (\text{内部顶点数}) + \frac{1}{2} \times (\text{边界顶点数}) + 0 \\ &= 3(m-1)(n-1) + \frac{1}{2}\left(2(m-1) + 2(n-1)\right) \\ &= 3(mn - m - n + 1) + (m - 1 + n - 1) \\ &= 3mn - 3m - 3n + 3 + m + n - 2 \\ &= 3mn - 2m - 2n + 1 \end{aligned}
然而，网格的几何结构决定了并非所有顶点能同时达到最大值。我们需要减去必须损失的部分。

3. 几何约束与路径引理

3.1 定义与引理

我们引入原题中的引理：

  • 定义 - 最大状态（Maximum）： 如果内部顶点值为 3，或边界顶点值为 1/2，称该顶点处于最大状态。
  • 定义 - 路径（Path）： 沿着网格线的一系列顶点，使得相邻顶点之间距离为一个单位边长。
  • 引理： 在网格的任何染色方案中，任何一条从水平边界出发、在垂直边界结束且不经过角点的路径，必然包含至少一个非最大状态的顶点。

引理简证： 假设路径上所有顶点都是最大状态。如果确定了路径起点的方格颜色，沿着路径推导，由于每个顶点都是最大状态（意味着局部颜色结构固定），路径上所有方格的颜色将被唯一确定。对于从水平边走到垂直边的路径，这最终会导致矛盾（通常导致最后一个顶点的局部染色无法满足最大值条件，或者值为0）。

3.2 损失量的计算

每一个“非最大状态”的顶点会导致总和 SS 减少：

  • 如果该顶点在边界，值由 1/21/2 变为 00，损失 1/21/2。
  • 如果该顶点在内部，值由 33 变为 ≤2\le 2，损失至少 11。

因此，每一条满足引理条件的独立路径，至少会导致总和比 SboundS_{bound} 减少 1/21/2。

3.3 构造独立路径

不妨假设 m≤nm \le n。我们需要在网格中找到尽可能多的互不干扰（顶点不重合）的路径，这些路径均连接水平边界和垂直边界。

我们利用矩形的两个对角区域来构造两组路径：

第一组（左下角区域）：
连接下边界（水平）和左边界（垂直）。
我们可以构造 m−1m-1 条路径。对于 k=1,2,…,m−1k = 1, 2, \dots, m-1：

  • 路径 PkP_k 连接底边顶点 (k,0)(k, 0) 和左边顶点 (0,k)(0, k)。
  • 这些路径围绕左下角 (0,0)(0,0) 呈 L 形嵌套。
  • 由于 k<m≤nk < m \le n，这些路径均在网格范围内。

第二组（右上角区域）：
连接上边界（水平）和右边界（垂直）。
我们可以构造 m−1m-1 条路径。对于 k=1,2,…,m−1k = 1, 2, \dots, m-1：

  • 路径 QkQ_k 连接顶边顶点 (n−k,m)(n-k, m) 和右边顶点 (n,m−k)(n, m-k)。
  • 这些路径围绕右上角 (n,m)(n, m) 呈 L 形嵌套。

路径的独立性：

  • 第一组路径占据的区域大致满足 x+y≤2(m−1)x + y \le 2(m-1)。
  • 第二组路径占据的区域大致满足 x+y≥(n+m)−2(m−1)x + y \ge (n + m) - 2(m-1)。
  • 由于 m≤nm \le n，这两组路径在空间上是分离的，没有公共顶点。
  • 总共有 2(m−1)2(m-1) 条独立路径。

3.4 最终计算

根据引理，每条路径至少贡献 1/21/2 的损失（Deficit）。
总损失 DD 为：

D=(路径数量)×12=2(m−1)×12=m−1D = (\text{路径数量}) \times \frac{1}{2} = 2(m-1) \times \frac{1}{2} = m - 1
因此，最大可能的和 SmaxS_{max} 为：

Smax=Sbound−D=(3mn−2m−2n+1)−(m−1)=3mn−3m−2n+2\begin{aligned} S_{max} &= S_{bound} - D \\ &= (3mn - 2m - 2n + 1) - (m - 1) \\ &= 3mn - 3m - 2n + 2 \end{aligned}
由于我们假设了 m≤nm \le n，上述公式中的 −3m-3m 实际上是 −2m−m-2m - m，即 −2m−min⁡(m,n)-2m - \min(m, n)。
若 n<mn < m，同理可得减去的是 n−1n-1。

4. 结论

综合上述推导，对于任意 m×nm \times n 网格，扫雷数字的最大和为：

Smax=3mn−2m−2n+2−min⁡(m,n)S_{max} = 3mn - 2m - 2n + 2 - \min(m, n)

验证

  • 当 m=nm = n 时：
    3n2−2n−2n+2−n=3n2−5n+23n^2 - 2n - 2n + 2 - n = 3n^2 - 5n+2