特殊构型可推性科普

2024/05/031206 浏览综合

鉴于有的人宁可大篇幅地跟我抬扛也不愿意自己试着推理一下，所以我单开一帖给大家讲一些出现几率极小但是又很有特色的特殊构型的结论

1 图示的四种构型全部可推。我们知道，开局时的第一次点击一定是0，即第一次点击一定会打开至少3×3的区域。以左上角构型为例，可推指首次点击打开如左上构型的区域时，有至少一个格子可以确定非雷，且存在一种雷的排布使得打开所有确定为非雷的格子后仍可保证推理继续进行。另外三种构型同理。具体哪些格可推给各位留作练习。

1.1 左上角构型在最理想状态下出现几率为1/100000数量级，不知道有的人张嘴来一句很简单就能找到是怎么想的。

2 1的结论可以推广。在第一次点击打开矩形区域的情况下，若矩形一边长为3的正奇数倍，另一边长为3的正整数倍，且边界上所有线索均为1，则该构型是可推的。证明留给各位留作练习。

3 1和2的结论可以推广。在第一次点击打开矩形区域的情况下，若矩形边长m，n满足m=0或1(mod3)且n=0或1(mod3)，且边界上所有线索均为1，那么该构型有至少一个格子可以确定为非雷。证明留给读者作为练习。

3.1 为什么总是和3的倍数有关？这是一个与传递性有关的特殊性质，通过这个性质以及一些更复杂的结构可以构造一个图灵完备的计算系统。