@ 2020.03.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 < n.length; i++) { for (j = i; j < n.length; j++) { for (k = j; k < n.length; k++) { a=[i,j,k]; if(new Set(a).size == 3){ b=[0,1, 2,3,4,5,6]; b.splice(i, 1); b.splice(j, 1); b.splice(k, 1); y = eval(a.join("+"))%7; d[y].push(a.join(",")); if(new Set(b).size == 4){ e[y].push(b.join(",")); } } } } } d.forEach(function(items,index){ console.log("當余數為"+index+"的時候小明有:n%c"+items.join("n")+"n%c"+"可以很明顯的看出機器人不拿的是哪一張,小明的可能性都是2種。而此時小紅和機器人實際拿到其他牌的所有可能為%c"+e[index].join("或")+"%c,小紅可以很容易的從手中的牌得出機器人的牌。n",'color:#f00','color:#000;','color:#f00','color:#000;'); })

我用瀏覽器的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型游戲提供了一個完全安全的加密技術的最簡形式模型。


支付寶打賞 [x]
您的大名: 打賞金額:

贊一個 (15)
猫先生 <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <文本链> <文本链> <文本链> <文本链> <文本链> <文本链>