399718奇闻趣事网majer 【奇闻趣事网】399718.com03.29 , 10:00
脑力小体操：病毒是否能感染整个沙盘
为了避免头重脚轻，这次先给出本期的问题。
设想设计一款简化版的瘟疫公司山寨手游。比如说，把全世界看成是100×100的棋/沙盘。每个方格是一个行政区域。因此，一个行政区域至多有4个共边界的邻居。
然而，因为人力有限，同时无法完全杜绝人员往来。所以，只要某个区域有2个邻居爆发疫情，则该区域必然无法幸免。
开局的时候，作为上帝的玩家——你——可以随意地选出99个区域作为起爆点。
现在的问题是，你能否通过巧妙地选择初始位置，让沙盘完全沦陷？
本轮问题极难，但是如果找到了正确的视角，就能直接秒杀。
bigminions：撸了个页面测试自己的想法， 结果原来想法发现不对的
上一期：推理机器猜纸牌
原始问题来自2000年的莫斯科数学奥林匹克竞赛。
游戏具体的规则如下：0. 在主持人说开始之前，所有人不得出声；
0.1 增加规则，小明必须陈述一个可被机器人检验的真命题；(事先考虑到大家会利用图灵测试的思路骗过机器人，既然这一思路已经在评论区里被提了出来，其它同性质的解答也大同小异了，就把规则增补上)
1. 一共有7张牌面已知的牌。为了方便叙述，不妨将其当做是A0，1，2，3，4，5，6；(应把A改成0)
2. 稍后，小明和小红的眼前会各具现出3张纸牌若干秒，他们必须牢牢记住(不妨设小明是1，2，3)；
3. 推理机器也同时会得到一张纸牌，而小明小红无法得知是哪张；
4. 主持人说开始之后，小明有5分钟的时间，想出并说出一句话；
5. 当小明发言的时间结束后，推理机器将进行判定，如果他能从小明的话语中猜出属于小明或小红的任意一张牌(它当然知道两人一共持有哪6张牌，但是之前无法确定具体哪张牌归属哪个人，现在就是进行此类判定)，则小明和小红落败；
6. 如果推理机器无法作答，则轮到小红发言，小红需要指出推理机器持有的是那张牌；如果小红说错，则两人依然落败；反之则通关。
ID为Anon朋友率先给出了一个答案：
首先的想法就是把自己手牌的和报出来，这样在一般情况下可以(小红从总数中减去小明的和与自己的和即可)，但如果我报了个6就不行了(只有1+2+3可能)
于是我们可以用xor，与加法一样可交换所以小红一定猜得出来，而机器人猜不猜得出来就变成了下面这个问题：
我知道三个1-7的数的异或的结果，我还能排除一个数，我能不能再定出一个数不在这三个数中(@于小明报了相当于小红报了，我们就只考虑一边了)?
答案是不可能，我们对问题稍微做一点变化：知道三个0-7的异或为a，并且能排除其中两个数bc，能不能再定出一个不在这三个数中?(相当于把0看作是固定排除掉的，问题的等价性可以通过把新问题中所有数异或上第一个排除的数得到)
此时利用反证法，假定我判断出了某个数一定不在其中，不妨这个数是0(否则异或掉化归)。此时相当于在说不存在两个数非bc的数xy的异或是a(否则0xy可以为小明所有)，但我们知道bc加在一起一共排除掉了至多四个数不在xy中(b/c/b^a/c^a)，所以还剩4个数可以选，与数全都排除完了矛盾。
如果7张变成5张(2/2/1)，则上面的方法不适用(刚好排除完)，至于此时机器人是否必胜我就不清楚了。
或者
直接手牌点数和mod7。
然后，ID为一一的朋友用js写了一段验证代码：
/*
楼上的大佬的解答看了半天没有想懂，十分不服气的我想要写个穷举列出所有的可能性。最后得到结果居然是正确的！但是我还是不知道为什么能这样解答。。。JS代码附上
*/
var d = [[],[],[],[],[],[],[]];
var e = [[],[],[],[],[],[],[]];
var n = [0,1, 2,3,4,5,6];
for (i = 0; i
我用浏览器的F12调出的控制台运行上述程序，输出如下：
当余数为0的时候小明有：
0,1,6
0,2,5
0,3,4
1,2,4
3,5,6
可以很明显的看出机器人不拿的是哪一张，小明的可能性都是2种。而此时小红和机器人实际拿到其他牌的所有可能为1,2,3,5或0,2,4,5，小红可以很容易的从手中的牌得出机器人的牌。
VM78:26 当余数为1的时候小明有：
0,2,6
0,3,5
1,2,5
1,3,4
4,5,6
可以很明显的看出机器人不拿的是哪一张，小明的可能性都是2种。而此时小红和机器人实际拿到其他牌的所有可能为0,2,3,5，小红可以很容易的从手中的牌得出机器人的牌。
VM78:26 当余数为2的时候小明有：
0,3,6
0,4,5
1,2,6
1,3,5
2,3,4
可以很明显的看出机器人不拿的是哪一张，小明的可能性都是2种。而此时小红和机器人实际拿到其他牌的所有可能为0,1,3,5，小红可以很容易的从手中的牌得出机器人的牌。
VM78:26 当余数为3的时候小明有：
0,1,2
0,4,6
1,3,6
1,4,5
2,3,5
可以很明显的看出机器人不拿的是哪一张，小明的可能性都是2种。而此时小红和机器人实际拿到其他牌的所有可能为1,3,5,6，小红可以很容易的从手中的牌得出机器人的牌。
VM78:26 当余数为4的时候小明有：
0,1,3
0,5,6
1,4,6
2,3,6
2,4,5
可以很明显的看出机器人不拿的是哪一张，小明的可能性都是2种。而此时小红和机器人实际拿到其他牌的所有可能为1,3,4,6，小红可以很容易的从手中的牌得出机器人的牌。
VM78:26 当余数为5的时候小明有：
0,1,4
0,2,3
1,5,6
2,4,6
3,4,5
可以很明显的看出机器人不拿的是哪一张，小明的可能性都是2种。而此时小红和机器人实际拿到其他牌的所有可能为1,3,4,5或1,2,4,6，小红可以很容易的从手中的牌得出机器人的牌。
VM78:26 当余数为6的时候小明有：
0,1,5
0,2,4
1,2,3
2,5,6
3,4,6
可以很明显的看出机器人不拿的是哪一张，小明的可能性都是2种。而此时小红和机器人实际拿到其他牌的所有可能为1,2,4,5或0,2,4,6，小红可以很容易的从手中的牌得出机器人的牌。
感谢以上两位——以及之后几位——朋友给出的解答。
或许有些朋友想知道当时命题组推荐的解答。
命题人应用到了所谓的有限射影平面这一数学工具，可以解决推广的a+b+c型问题(原始问题是3+3+1型：玩家各3张牌，机器人手里有1张)
和评论里几个朋友的思路近似，小明给出这样一个真命题：我手里的牌型是如下
{0；1；4}、{0；2；5}、{0；3；6}、{1；2；3}、{3；4；5}、{1；5；6}、{2；4；6}
这几种之一。
在3+3+1的情形下，向量空间本质上和取模运算是一致的。实际上，此时的有限射影平面恰好是最基本的法诺平面。
最后说一下，这个游戏有啥特殊意义。
现在我们最常用的加密系统是RSA密码系统。RSA的安全性依赖于以下事实：对计算机而言，大数分解是非常困难的任务。
1994年，彼得·索尔(Peter Shor)开发了一种量子算法，该算法允许量子计算机在多项式时间内的完成整数分解。
因此，一旦有人制造出真正可用的量子计算机，RSA系统就面临淘汰的境地。
本轮的推理机器博弈，小明和小红可以看作是两个用户，在公共频道传递敏感信息，而推理机器则是窃听者。
@于没有私钥，且所有信息都是公开发布的，一般的a+b+c型游戏提供了一个完全安全的加密技术的最简形式模型。
本文版权归原作者，本站只做分享普及使用。若侵犯了你的权益，请提供版权有效证明，核实后下架删除。 (17)
未经允许不得转载：399718奇闻趣事网 » 脑力小体操：病毒是否能感染整个沙盘