引言
高级的最大IOE记录在多年前就被刷到3.372。
只是多年以后才由朱耀宇证明，IOE的上限为3.4。本文是对《扫雷中IOE的最大可能值及其证明》的内容的梳理，以及补充其中省略的步骤。采用严谨但是通俗的语言，力求使得更多的人能够容易地理解这个证明，了解为什么是这样。
原文的证明本身是正确的，其技巧是值得称赞的，同时本文也有一些改进。
下面给出证明的全部过程。
第一部分
定义一：鼠标左击、右击或双击均称为操作，分别记为L、R、D。
定义二：扫完一张图采用的步骤，删去其中的废操，其余的操作的序列称为操作序列，记为A=a1, a2,…, an，i=1,2,…,n，n为步骤数。
ai是一个二元组，记录了操作和坐标信息。比如（1，1）起手记为a1={L,(1,1)}。
定义三：雷图中若干cell的集合称为空间，操作ai导致若干cell的状态的改变，称改变状态的cell的集合为基于ai的空间单元，空间单元的cell个数称为空间大小。
定义四：将操作序列A，按照如下步骤分为若干个组：
1.首先将R操作分为不同的组，即每组中最多有一个R。
2.对于每一个D操作，任选一个相邻的R操作，归入该组。
3.对于一个L操作，若所在的cell上还有D操作，那么将这个L分到对应的D那组。
4.其余的L分到各自单独的组中。
则每组称为一个时间单元，时间单元的操作个数称为时间长度。因此时间单元共有三种，分别是只包含一个R，但是有若干个L和D的时间单元，称为第一类时间单元；只包含一个R，但是有若干个D的时间单元，称为第二类时间单元；只包含一个L操作的时间单元，称为第三类时间单元；只包含一个R的时间单元，称为第四类时间单元。
定义五：时间单元与基于该时间单元中每个操作的空间单元的总和，称为时空单元，时空单元的空间大小与时间长度之比称为时空单元的IOE，区别于总IOE，加上下标后记为IOEi。
第二部分
定理一：IOE≤max{IOEi}。
定理一的证明：由定义四，扫雷游戏的整个时空能够被严格划分为四类时空单元，因此总的IOE就是IOEi的加权平均，故得证。
此时，雷图的IOE上限问题化成了时空单元的IOE上限问题。
定理二：第三类时空单元的IOE=1<3.4。
定理二也是显然的。
引理：第三类时空单元对局面造成的影响，是降低或不改变其他时空单元的IOE。
引理的证明：首先要注意第三类时空单元的位置是不能双击的。然后这一类时空单元会减少其他D操作获得的cell，本身也无助于D操作的进行，故得证。
定理三：第四类时空单元的IOE=0<3.4。
这是显然的。
引理：第四类时空单元对局面造成的影响，是降低或不改变其他时空单元的IOE。
引理的证明：第四类时空单元就是一个已经标好的雷，这个单元的存在只会使得与其相邻的其他单元的D操作发生时，少打开一个cell。并且仅基于第四类时空单元的D操作是不允许的，因为这样就会使这个第四类时空单元变成一、二类，从而产生矛盾。综上，第四类时空单元会使得一个相邻的基于这个时空单元的R和另一个时空单元的R的D获得的cell减少1，故得证。
定理四：时空单元的空间单元的大小有限，必然限制在一个5*5区域内。
这是易证得的。
所以问题就化成了求第一、第二类的时空单元的IOE上限问题。
要考虑这个问题，由定理一和定理四，只需要在一个5*5区域内的情况。
另一方面，由定理二和定理三，可以不考虑单独的L、R对初始5*5区域状态造成的影响，只需要考虑第一、第二类的时空单元相互之间的影响。也就是说，直观地讲，初始5*5区域中既不存在由L（而不是LD）造成的支离破碎的边缘，也不存在除中心处的雷以外，任何其他被标出或未被标出的雷；而是只存在被D或Op制造出的边缘。由于Op的本质是对数字0的双击，所以只需要考虑D操作制造出的边缘对初始5*5区域状态造成的影响。
首先分析第一类时空单元的IOE上限。
定理五：第一类时空单元的IOEmax=3.4。
证明：第一类时空单元包含一个有D的L，这样的优势是，它可以在一个完整的5*5局部直接启动。无需详细的分析，我们可以直接用枚举法得到这一类时空单元的最大IOE，其步骤如图所示。
打开了17个3BV，操作为5，所以局部最大IOE为3.4。
随后，假设初始5*5区域不完整，有D操作造成的边缘，那么显然局部最大IOE达不到3.4。
因此定理五得证。
接下来分析第二类时空单元的IOE上限。
定理六：第二类时空单元的IOEmax=3.25。
证明：第二类时空单元利用且必须利用已有“地形”，省去了一个L。而初始5*5区域的“地形”，必须是能够仅用D操作生成的。所以，我们只需要枚举分析各类“地形”下，第二类时空单元能够达到的最大IOE。
可以分为以下三种情况，且它们严格优于其他情况，或者与其他情况对称。
（1）IOEmax=16/5=3.2
（2）IOEmax=13/4=3.25
（3）IOEmax=12/4=3
具体操作步骤省略，读者可以很容易地自行验证。
因此定理六得证。
（注：原证明中“D1与组内所标雷相邻”的情况可以由上述三类情况包括，此处不再赘述，读者自行思考就能明白。）
因此，根据定理一、定理二、定理三、定理五、定理六，得出IOE≤3.4。
最后，让我们来构造一张IOE=3.4的图，如图所示：
同理可以构造任意大小的IOE=3.4的图，只要四周布满雷。
综上，得
定理七：对于面积足够大、且有限的雷图，不论其中包含几个雷，以何种方式排布；且不论何人，以何种方式扫，都有IOE≤3.4；取等号的条件与图中雷的数量有关，而与图的大小无关。
|
|
