甲,乙,和一台電腦進行一個遊戲,尋求甲乙兩人必勝的策略?

甲乙和電腦輪流出數字0或1(順序:甲,乙,電腦),如果在一輪遊戲中三者的數字是一樣的則甲乙贏,三者均出完才能進行下一局,甲乙可以在遊戲開始前討論策略,但在遊戲開始後就不能討論,電腦在遊戲開始時就已決定了出數字的順序,乙在比賽開始後會知道電腦的出數字的順序,但他不能告訴甲,只能通過他們的策略進行遊戲,試求保證以下勝場的策略:

1)5局勝3局

2)8勝5

3)9勝6

4)13勝9

5)18勝13

前三種已有解決,後兩題待解決


感謝邀請。

數月前寫的9局6勝的答案,作者本人。

利用同樣的分組策略(1,3,3,3……),可以確保對於所有的3n+1與3n+2局的比賽中,猜錯次數均不超過n+1。

對於任意3n+1,我們分成了1,3,3,3……共n+1組;

對於任意3n+2,我們分成了1,3,3,3……3,1共n+2組;

使用上文的策略,我們均可以確保猜錯次數控制在n+1以內。

題目中的13局9勝儘管也是3n+1的情況,但所需勝局數要求更多,需要重新構築答案。

18局13勝是最麻煩的3n問題,相當於需要尋找足夠多的違約特例,以標識出最後2局的信息,以及至少一組三局的全部勝利,也需要重新構築答案。

首發地址:文章

憑藉友誼,約定,合作,和不可或缺的背叛者,去戰勝邪惡莊家的問題。

問題:

出典:IBM Ponder This

涉及知識:情報/密碼學

說Alice和Bob兩人被迫參加一個邪惡的賭局,規則是這樣的:

Alice猜一個數0或1並公開,然後Bob猜一個數0或1並公開,然後庄家翻開公布事先已經藏好寫在紙上的一個數字0或1,只有這三個數都相等時,Alice和Bob才視為贏。

如果Alice和Bob兩孩子特別傻,就悶頭亂猜,那麼一局裡贏的概率顯然只有25%。

如果Bob比較聰明,看Alice猜什麼自己就跟著猜什麼,那麼一局裡贏的概率立刻會上升到50%,效率高多了。

然而,如你所知,上文里的數字都是概率,即使50%概率獲勝也可能屢戰屢敗慘死。

明天比賽就要開始了,今晚Bob得到了一個振奮人心的好消息:

明天比賽開始後,Bob有內線,可以拿到莊家藏好的紙上所有的情報(即包括了從第一局到最後一局所有的答案)!

但是比賽一旦開始,Alice和Bob就再也無法交流,只能眼睜睜的看著他們選擇了0還是1。

那麼,Alice和Bob開始討論,他們有什麼辦法,可以確保在明天的9局比賽里,贏下至少4局呢?

哦,這個問題並不複雜,Bob大可以放棄第1357局,不管Alice猜了什麼,Bob都明確給出下一局莊家藏起來的數字,然後第2468局Alice和Bob只要一起猜這個數字,就可以安定的拿下來4局,可喜可賀,可喜可賀。

多麼好的策略,但還是不夠。

明天的9局比賽里,Alice和Bob要至少拿下6局,才能逃出升天。

現在,商量一個辦法,讓兩個人都能活命吧。

解答:

用以下方案的思路,可順利的解決7局4勝,8局5勝的問題,有關9局6勝的問題下文將詳細討論。

對於7局,拆分成1,234,567三組。

對於8局,拆分成1,234,567,8四組。

對於9局,拆分成1,234,567,89四組。

——————

約定策略1:無論何時,當Alice猜的數字與莊家一樣時,Bob放棄傳遞情報,轉而出示與Alice一樣的數字,以確保拿下這一局。

例1:第4局Bob得知莊家數字為0,只要Alice出示0,Bob即跟進出示0以拿下這一局。

——————

約定策略2:一般而言,當Alice已知某情報的前提下或第1局時,出示的數字與莊家不同時,Bob開始傳遞情報,B出示『下面1組中莊家次數較多的數字』,A在下1組中連續3次均出示此數字。除非遭遇策略3的情況。

例2:第1局Alice猜1,實際莊家為0,則Bob出示234局裡出現較多的數字如0,之後234局中Alice全部出示0。

——————

約定策略3:當Alice由於之前數局一直猜對,導致下一組的第一局或第二局開始時沒有情報且猜錯時,Bob開始傳遞情報,Bob出示『本組內尚未猜測的局數中,莊家出現至少一次的數字』,Alice在本組內持續出示此數字。

例3.1:第1局Alice猜對,第2局Alice在沒有任何情報的條件下猜1,實際234三局為001,Bob出示34兩局中出現了至少一次的數字0(1亦可),Alice在接下來的34兩局中均出示0。

例3.2:續上例,第3局Alice猜對,第4局Alice已持有Bob例3.1所出示的情報,此時繼續出示0雖然錯誤,但Bob繼續依照約定策略2提供下一組567局中出現較多的數字。

——————

按照以上策略進行,在7局,8局的情況下,我們可以確保猜錯次數不超過3,解釋如下:

1)如果第1局猜錯,可傳遞234局的情報——————————————————————累計錯題1

1,1)(由約定策略2)第234局全部猜對,無法傳遞567局的情報————————累計錯題1

1,1,1)(由約定策略3)第567局猜錯2個,且傳遞了第8局的答案————累計錯題3

1,1,2)(由約定策略3)第567局猜錯1個,無法傳遞第8局的答案————累計錯題3

1,1,3)第567局全部猜對,無法傳遞第8局的答案————————————累計錯題2

1,2)(由約定策略2)第234局猜錯一個,可傳遞567局的情報——————————累計錯題2

1,2,1)(由約定策略2)第567局全部猜對,無法傳遞第8局的答案————累計錯題3

1,2,2)(由約定策略2)第567局猜錯1個,且傳遞了第8局的答案————累計錯題3

2)如果第1局猜對,無法傳遞234局的情報————————————————————累計錯題0

2,1)(由約定策略3)第234局全部猜對,無法傳遞567局的情報————————累計錯題0

2,1,1)(由約定策略3)第567局猜錯2個,且傳遞了第8局的答案————累計錯題2

2,1,2)(由約定策略3)第567局猜錯1個,無法傳遞第8局的答案————累計錯題2

2,1,3)第567局全部猜對,無法傳遞第8局的答案————————————累計錯題1

2,2)(由約定策略3)第234局猜錯1個,無法傳遞567局的情報————————累計錯題1

2,2,1)(由約定策略3)第567局猜錯2個,且傳遞了第8局的答案————累計錯題3

2,2,2)(由約定策略3)第567局猜錯1個,無法傳遞第8局的答案————累計錯題3

2,2,3)第567局全部猜對,無法傳遞第8局的答案————————————累計錯題2

2,3)(由約定策略3)第234局猜錯2個,可傳遞567局的情報————————累計錯題2

2,3,1)(由約定策略2)第567局全部猜對,無法傳遞第8局的答案————累計錯題3

2,3,2)(由約定策略2)第567局猜錯1個,且傳遞了第8局的答案————累計錯題3

如此,此樹狀圖覆蓋了依照此3條約定策略後,7局,8局中的所有情況,可以確保猜錯次數不超過3,即可以確保7局4勝與8局5勝的情況。

利用同樣的分組策略(1,3,3,3……),可以確保對於所有的3n+1與3n+2局的比賽中,猜錯次數均不超過n+1。

對於任意3n+1,我們分成了1,3,3,3……共n+1組;

對於任意3n+2,我們分成了1,3,3,3……3,1共n+2組;

使用上文的策略,我們均可以確保猜錯次數控制在n+1以內。

遺憾的是,此策略對於9局是行不通的,因為9局比賽的最後一組內包括2局,若這2局為00和11還好,一旦是01或者10,是無法用簡單的一句話情報告知這兩局的答案的。

我們可以使用部分補救措施以解除這種尷尬局面

————

補救措施1:一旦第1局猜對,我們就將這第1局拋棄,對剩下的8局視為一個新的3n+2局問題,從8局裡確保5局勝利,總共勉強的拿到6局勝利。

補救措施2:一旦第1局猜錯了,但234局都猜對了(目前對了3局),我們將這4局拋棄,對剩下的5局視為一個新的3n+2局問題,從5局裡確保3局勝利,總共勉強的拿到6局勝利。

補救措施3:一旦第1局猜錯了,第234局也錯了一個,但第567局都猜對了(目前對了5局),我們將這7局拋棄,對剩下的2局視為一個新的3n+2局問題,從2局裡確保1局勝利,總共勉強的拿到6局勝利。

————

遺憾的是,即使有如此完善的補救措施,還是未能覆蓋所有情況,即沒有出現任意一組完全正確的情況,這種情況的確尷尬。

簡單列舉一例補救措施也行不通的最差的情況如下:1,001,100,10

1)第1局猜錯,傳遞234局的情報——————————————————————————累計錯題1

2)234局猜錯1個,傳遞567局的情報————————————————————————累計錯題2

3)567局猜錯1個,傳遞89局的情報失敗(如89局是01,此時只傳出了1的消息)————累計錯題3

4)89局按照之前策略繼續出示,但只猜對了1個————————————————————累計錯題4

為了解決這種極限最差的情況,下面我們使用最終手段:違約特例。

違約策略何時使用?當9局分組為1,234,567,89後,一旦Bob發現234不全相同,567不全相同,且89不同時,Alice只要第1局猜錯,按照約定策略繼續進行下去,必然無法觸發補救措施,必然會迎來極限最差局面。此時Bob就應該開始執行違約特例。

我們以567三局不全相同為突破口,根據其中的少數派的位置來執行違約特例(如567三局結果為001,則少數派位置為7)。

————

違約特例1:當567三局的少數派位置為5時

Bob執行違約動作:在234三局之中,在本應確保正確的2局之一故意出示錯誤的數字。234三局之中其餘2局的行為照常,如果選擇違約的局數在『本應確保正確的2局』之中靠前,則意在傳播89兩局的答案為10,否則為01。

例1:針對1,001,100,10的答案:

Bob發現此局面是違約特例後,在Alice第1局猜錯後,Bob提示234局的情報為0,且在第2局面對正確答案0時,故意出示1,則Alice發現第2局自己出示0,Bob出示1,莊家出示0,此為明顯的違約動作。儘管第2局告負,其後的34兩局照常按照約定策略進行。

Alice發現此違約動作後,了解到的情報如下:

1)567局中的少數派位置為5;

2)89局的答案為10;

3)在34局照常進行完畢後,Alice照常得到567局自己應出示0的情報,結合1)可判斷出567三局的答案為100。

因此,Alice第1局答錯,第2局被犧牲,導致前4局裡只拿下1局的不利情況下,可以確保之後的56789五局全部獲勝,累計取得6勝。

如果89的答案為01,則B將會在第2局照常行事,第3局違約,第4局傳播567局的情報。

————

違約特例2:當567三局的少數派位置為6時

Bob執行違約動作:在第1局後,傳遞關於234局錯誤的情報,即傳遞234局中數字較少的答案。且在234局中A一定答錯的2局中,靠前的1局傳遞567局的情報,靠後的1局傳遞89局的情報:如為1則89兩局的答案為10,否則為01。

例2:針對1,001,010,10的答案:

Bob發現此局面是違約特例後,在Alice第1局猜錯後,Bob提示234局的情報為1;且在第2局當Alice出示1後,自己出示567局的情報0;且在第3局當Alice出示1後,自己出示89局的情報1。則Alice在第3局結束後發現儘管B在第1局後傳遞的情報為1,卻連續遭遇兩次錯誤答案,此為明顯的違約動作。

Alice發現此違約動作後,了解到的情報如下:

1)567局中的少數派位置為6;

2)567局的情報為0;

3)89局的答案為10;

4)由1)和2),567三局的答案可確認為010。

因此,Alice第1局答錯,第23局被犧牲,導致前4局裡只拿下1局的不利情況下,可以確保之後的56789五局全部獲勝,累計取得6勝。

如果89的答案為01,則B將會在第3局裡出示0。

————

違約特例3:當567三局的少數派位置為7時

Bob執行違約動作:在567三局之中,在本應確保正確的56兩局之一故意出示錯誤的數字。如果選擇違約的局數為第5局,則意在傳播89兩局的答案為10,違約的局數為第6局則意在傳播89兩局的答案為01,且第7局按照莊家的正確答案執行。

例3:針對1,001,110,10的答案:

Bob發現此局面是違約特例後,在Alice第1局猜錯後,第4局後Bob提示567局的情報為1,且在進入第5局之後,面對正確答案1時,故意出示0,則Alice發現第5局自己出示1,Bob出示0,莊家出示1,此為明顯的違約動作。

Alice發現此違約動作後,了解到的情報如下:

1)567局中的少數派位置為7;

2)89局的答案為10;

3)由之前獲得的567局情報為1,得知第6局應繼續出示1,第7局改為出示0;

因此,Alice第1局答錯,第234局答對2題,第5局被犧牲,但之後的6789四局均可答對,累計取得6勝。

如果89的答案為01,則B將會在第6局裡出示0。

————

由以上的3條約定策略,3條補救措施,3條違約特例,即可完整覆蓋9局遊戲中所有情況,可確保無論多麼糟糕的情況下均可取得6勝。

Alice和Bob終於逃脫生天,重獲自由,可喜可賀。

問題在Matrix67的Blog上發現,重新整理自IBM Ponder This的答案。


五局三勝:只要乙第一局出電腦第二局,第三局,第四局中多的那個數,即1或0,甲第一局不一樣,但第二三四局都出乙第一局出的,若二三四局電腦都出1或0,則甲乙勝利,若電腦出了2個一樣的,乙就在電腦出另一個不一樣的時候出最後一局電腦出的,這樣甲就知道最後一句出什麼,就贏了三局。

九局六勝的策略:http://card.weibo.com/article/h5/s?from=timelineisappinstalled=1#cid=1001603984059859653404vid=extparam=from=wm=0ip=182.18.36.16,感謝提供


如果下一局選0,則乙馬上選本局正確答案。

如果下一局選1,則乙先等10分鐘再選本局正確答案。

增加一個維度即可


第一行是輸的局數,第二行是只輸這麼多局情況下最多能保證玩多少盤。

例如前五行:2局1勝,5局3勝,8局5勝,9局6勝,13局9勝,18局13勝。最後一行:150局119勝。

這個結果很有趣,甲完全不知道電腦要出什麼數的情況下,可以和乙配合的保證150局裡拿下119局。

這是做完題後,寢室同層的哥們給寫的程序輸出的結果。第一列可以忽略掉。總共2行,31列,寫不下了排版成三大行。

如果關注的人多我會把答案寫詳細。可能說到寫代碼,很多人就已經容易有思路了。


以下給出前四題答案。有更新的可能。

(1)五輪必勝三輪。

整道大題的基礎技巧:以本小題為例,乙看第2~4輪,裡面必定有一數比另一數出現更多次 (要麼3比0,要麼2比1) 。那麼他第一輪就出什麼就看是2~4里出現得更多次的數,然後甲第2~4輪只要連出三次該數即可,保證最少中兩次。

以下是本題答案:

使用上述套路,然後乙在2~4輪不中那輪 (或2~3全中時的4) 出第5輪的數。甲第5輪出該數,勝。加上2~4輪的兩勝,共三勝。

不妨總結為【5=1+3+1】,以下會使用類似的式子。

(PS:當然,可以將情況分為2~4輪數字相同與不全相同來討論,做到步步緊逼可勝就勝。不過兩者結果是一樣的,於是這裡為了減少文字,不分別討論了。下同。)

(2)八輪必勝五輪。

用1提示2~4,用2~4不中那輪 (或2~3全中時的4) 提示5~7,用5~7不中那輪 (或5~6全中時的7) 提示8。

總結為【8(5)=1(0)+3(2)+3(2)+1(1)】

(3)九輪必勝六輪。

對於此題,之前的套路已經明顯不夠用了,要引入一種高階技巧:故意輸掉在本該勝的輪。簡單來說包括兩個手段:1.故意提示錯誤的數;2.在甲出數與電腦相同時故意出錯數。將這兩個手段以各種方式運用,甚至進行組合,以傳遞更多的信息,用小的犧牲換取大的勝利。具體怎麼做呢?往下看,請大家自行領悟。

(PS:使用本技巧很容易出錯的點在於,在某種情形下兩個不同分支走到某一步得到的結果是一樣的,這會導致甲無法判定情況。請務必避免這種錯誤。事實上這種錯誤有一些簡單的判定法,諸位可自行探索。)

以下是本題答案:

把所有情況分為六個分支:

一、2~4相同,則用1提示2~4得三勝,然後5~9共5輪必得三勝。

【9(6)=1(0)+3(3)+5(3)】

二、2~4兩同一異,5~8相同,則用1提示2~4得兩勝,然後用2~4必輸輪提示5~8得四勝。

【9(6)=1(0)+3(2)+4(4)+1(0)】

三、2~4兩同一異,5~8三同一異,則用1提示2~4得兩勝,然後用2~4必輸輪提示5~8得三勝,最後用5~8必輸輪提示9。

【9(6)=1(0)+3(2)+4(3)+1(1)】

剩下三個分支都是2~4兩同一異,5~8兩同兩異:

四、5~8的格式為AABB

(AB分別為01或10),則用1提示2~4得兩勝,然後用2~4必輸輪提示A,但是在5~6乙故意出錯一輪,提示甲在7~8改出B得兩勝。最後9甲出啥則看5或6乙哪輪出錯,5錯則9為0,6錯則9為1。共得2+1+2+1=6勝。

【9(6)=1(0)+3(2)+2(1)+2(2)+1(1)】

五、5~8的格式為ABAB,則用1提示2~4得兩勝,但在2~4乙故意出錯一輪,提示甲在5~8出ABAB。至於出啥則看乙哪輪出錯,先錯則0101,後錯則1010。最後用2~4必輸輪提示9,共得1+4+1=6勝。

【9(6)=1(0)+3(1)+4(4)+1(1)】

六、5~8的格式為ABBA,則用1提示2~4的少數得一勝,這樣甲在2~4共錯兩輪,乙先後提示兩次,第一次告訴甲5~8該答0110還是1001,第二次提示9,共得1+4+1=6勝。

【9(6)=1(0)+3(1)+4(4)+1(1)】

綜上,就是九輪必勝六輪的策略了。

(4)十三輪必勝九輪。

六大分支:

一、2~4相同,則用1提示2~4得三勝,然後5~13共九輪必得六勝。

【13(9)=1(0)+3(3)+9(6)】

二、2~4兩同一異,5~8相同,則用1提示2~4得兩勝,然後用2~4必輸輪提示5~8得四勝,最後9~13共五輪必得三勝。

13(9)=1(0)+3(2)+4(4)+5(3)】


剩下四大分支都是2~4兩同一異,5~8三同一異或兩同兩異。為方便表述可如下代入字母 (每種字母代表0或1) :

三、2~4={2a1b},5~8={3c1d}

四、2~4={2a1b},5~8=[ccdd]

五、2~4={2a1b},5~8=[cdcd]

六、2~4={2a1b},5~8=[cddc]

這裡{2a1b}=[aab/aba/baa],{3c1d}=[cccd/ccdc/cdcc/dccc]。


從「九輪勝六輪」方案可以看到,這四大分支都是2~8里得五勝,最後9再得一勝,可總結為【9(6)=1(0)+7(5)+1(1)】。

現在看9~12這4輪的格式,一共有五種:


{4e} {3e1f} [eeff]
[efef] [effe]

① 如果是前三種,前面1~8可以沿用「九輪勝六輪」方案,但是本來提示第9輪的地方改為提示e,然後繼續沿用「九輪勝六輪」方案里用過的技巧,{4e}可以得四勝,{3e1f}可以得三勝兼提示第13輪,[eeff]可以在9~10故意輸一輪提示11~12改成ff兼提示第13輪,保證9~13里最少得四勝。

【13(9)=1(0)+7(5)+4(4)+1(0)】

【13(9)=1(0)+7(5)+4(3)+1(1)】

【13(9)=1(0)+7(5)+2(1)+2(2)+1(1)】

②如果是後兩種[efef/effe],則必須改一下前面1~8的答法,如下:

三、2~4={2a1b},5~8={3c1d},本來是用1提示a,再在b那輪提示c的,現在改為用「九輪勝六輪」里第五、六分支的方法提示出[cdcd/dcdc/cddc/dccd]四種格式里其中一種,務求跟5~8里的{3c1d}只有1輪不同而且跟9~12搭配 (即[cdcd/dcdc]配[efef],[cddc/dccd]配[effe]) 。2~4本來提示9的改為提示e,然後5~8里必輸輪提示13,共得1+3+4+1=9勝。

【13(9)=1(0)+3(1)+4(3)+4(4)+1(1)】

(貼心舉例:如5~8=[ccdc],9~12=[efef],則乙可以利用1~4提示甲5~8出[dcdc]及e,再利用5提示13。)


四五六、2~4={2a1b},5~8=[ccdd/cdcd/cddc],則用1提示a,再在b那輪看9~12,如[efef]則提示c,[effe]則提示d。這樣5~8必輸兩輪,可用來分別提示e和13,共得2+2+4+1=9勝。

【13(9)=1(0)+3(2)+4(2)+4(4)+1(1)】

(再來貼心舉例:如5~8=[cddc],9~12=[effe],則乙可以利用1~4提示甲5~8出[dddd],再利用5提示e、8提示13。)

綜上,就是十三輪必勝九輪的策略了。

(5)十八輪必勝十三輪。

我沒有試著去解這道題。但可確認 @itfrombit 已解決本題,可惜目前他並未公布答案。

轉一下原話:「18出13能做到,不過太太複雜,即使我寫出來,恐怕也沒人有耐心看」。(默默吐槽,大神就是牛逼……)

本答案基本基於 @毒酒滴凍鴨 的解答,有改動,如有因此而帶來的疏漏,請指正,謝謝。

(PS:許多人寫過本題(中某幾個小題)的各種解答,包括本人。選取鴨神的解答為模板是因為個人認為他的答案在向上推廣的時候便於理解。)

————————————分割線————————————

關於題目:

最初的原題已經由 @往生已逝 在他的答案中提及,此處不再贅述。

事實上就我所知,題主的題目是間接從本人處得到,傳遞過程中未免有變化,導致一些不嚴謹或者不清晰,因而評論里有人吐槽……

這裡給出我編輯的題目格式,個人覺得足夠簡明而嚴謹。

甲乙與電腦進行對抗遊戲。

遊戲規則:遊戲有多輪,在一輪中,甲先出一個數,然後乙出一個數,最終電腦出一個數,數只能是0或1,一旦出數,該數對所有人可見。若甲乙電腦出的數皆一致,則該輪甲乙方勝,否則電腦勝。

已知電腦在整局遊戲中每一輪要出的數在對抗前都已決定,且乙可以獲知該數字序列。甲知曉乙可以獲知數列這一事件。在獲取數列後甲乙無法以任何形式交流且必須立即開始對抗。將時間或數字格式等作為信號皆視為交流。

以下有在相互獨立的五局輪數不同的遊戲中甲乙想達成的目標。請在甲乙尚可交流時,分別為每種情況設計出數方案,使得甲乙能達成目標:


(1)五輪必勝三輪。


(2)八輪必勝五輪。


(3)九輪必勝六輪。


(4)十三輪必勝九輪。


(5)十八輪必勝十三輪。

附加證明題:


(6)請證明:不存在十輪必勝七輪的出數方案。

(7)請證明:不存在十四輪必勝十輪的出數方案。

可以看到,最後還有兩道證明題。已由 @itfrombit 強勢構建本題的通用模型以證明。答案暫且不表,且等他日更新。

(PS:@不出來的人的ID不是知乎ID,我也不知道各位大大有木有註冊知乎賬號……)

相關鏈接:

「原題」-IBM Ponder This2013年9月謎題:IBM Research | Ponder This | September 2013 Challenge

(事實上,本題並非在IBM Ponder This上首發,但由於首發處已沒有該題,故以IBM Ponder This的鏈接作為「原題地址」。可在IBM Ponder This2013年9月謎題的解答看到:"The problem was posed several years ago on the RAD challenge site (the
site is not on-line anymore, see a news story about it at RAD offers $1,000 to 1st person to solve online brain teaser - Globes English.
MSRI has a nice mathematical puzzles corner and you can see a version of this challenge there too.")

Matrix67討論原題(9勝6)的博客:Matrix67: The Aha Moments

關於9勝6的討論與幾個解法及通用模型與10不勝7之證明(較瑣碎):你真的做過智力題?

從五勝三到十三勝九的詳細分析與解答:【題王】兩死囚合作猜牌題 (地獄難度)


13勝9解法 提供者:小清新

答案是一個朋友研究的,我只是轉發一下(並附帶有一點自己的修改,如果有錯的話歡迎指出)

將13局分為1|3|4|4|1,分別記做123456789ABCD

正常策略1:

在5678和9ABC的數字為3:1的情況下,乙在第一局傳遞234中的多數派,234敗局傳遞5678的多數派,以此類推

正常策略2:

在5678和9ABC這兩組中,若某一組為2:2,則傳遞關於該組數字的信息時默認傳遞第一次出現的數字,如果與違約特例矛盾,優先執行違約特例。

正常策略3:

若第一局蒙對,234正常贏兩局然後剩下的轉為9勝6

正常策略4:

若234三局電腦所出數字相同,剩下的轉為9勝6

正常策略5:

若5678電腦所出數字相同,剩下的轉為5勝3

正常策略6:

若9ABC電腦出數字相同,並且5678為2:2,則在234中傳遞567會出現兩次的那個數,並在5678的兩個敗局中分別傳遞9ABC和D的情報。

接下來是違約特例。

一、對於5678|9ABC為2:2|3:1的情況——

——5678四個數字的特點(A和B分別表示1,0中的一個,A和B不同)

ABBA 234中故意錯一個,靠前位置錯(以下簡稱前錯)表示5678=1001,靠後位置錯(以下簡稱後錯)表示5678為0110,原來本身的敗局(以下簡稱原錯)提示9ABC的多數派

ABAB 傳關於234的錯誤情報,前後敗局分別提示5678(1=1010,0=0101)以及9ABC的多數派

AABB 56中故意錯一個,本次以及以後遇到此情況(1234正常,但在5,6中乙故意錯了一個),甲將7和8反過來。前錯意在說明9ABC為1,後錯意在說明9ABC為0

二、對於5678|9ABC為2:2|2:2的情況——

——5678四個數字的特點(A和B分別表示1,0中的一個,A和B不同)

ABBA 5678前的預備工作:234故意錯一個,前後提示5678為1001,還是0110,原錯提示第9局的數字

——接下來,對9ABC的數字特點再分兩種情況

ABBA或ABAB 在5678四個數字中故意錯一個,5,6,7,8分別表示後面5局為 ABBA 1,ABBA 0,ABAB 1,ABAB 0

AABB 5678四個分全拿,在9,A中故意錯一個,前後分別表示D=1,D=0

ABAB 5678前的準備工作:傳關於234的錯誤情報,兩錯局分別提示5678為1010或0101,原錯提示第9局

——接下來,與5678=ABBA時策略相同,不再重複敘述

AABB

——9ABC四個數字的特點

ABBA 234錯局提示5,在5,6中故意錯一個,前後分別表示9ABC為1001還是0110,甲將7,8反過來。在7,8中再故意錯一個,7錯D=1,8錯D=0

ABAB 5和6不違約,7和8均會輸。敗局分別傳遞9ABC為1010或0101,以及D局

AABB 234錯局提示5,56中故意錯一個,傳遞9(前1後0),9A中再故意錯一個,傳遞D(前1後0)

三、最複雜的,對於5678|9ABC為3:1|2:2的情況——

——9ABC四個數字的特點

AABB 1~8全部正常,9和A中故意錯一個,9錯D=1,A錯D=0

ABBA 5678的三個正常局中,靠前違約表示9ABC為1001,居中違約表示9ABC為0110,原錯傳D

注:若5678為BAAA,ABAA則正常。AABA,AAAB則甲會將7和8反過來,但仍可以對一局

ABAB ——5678的少數派在

56 傳遞關於5678的假情報。第7局結束後甲發現情報是假的,8反過來。前敗提示9ABC為1010或0101,後敗提示D局

78 ——對於9ABC

1010 5678三個正常局中,靠後違約,原錯傳遞D局的信息。

0101 進入三種極限瘋狂模式

——對於5678和D

少數在7,D=1 234本該對的兩局都故意錯,原錯傳遞5678為0010還是1101,此後5局必為01011

少數在7,D=0 5和6全部故意錯,此時7,8甲已知,之後5局必為01010,全對。

少數在8 傳關於234的錯誤情報,並在原本對的一局也故意錯。前敗傳遞5678為0001還是1110,後敗傳遞D局

四、對於5678|9ABC為2:2|4:0的情況——

本來已經發布了,但突然發現不太對,因為約定策略6和其中一個違約特例有重複,無法區分,因此更正一下。

5678為ABAB和ABBA時都不會出事

當5678為AABB時,無法和9ABC為ABAB的情況區分開。於是進行最後一個違約策略。

傳關於234的錯誤情報,前後敗局分別提示5678的錯誤情報以及9ABC。到5678時,甲發現第一個就錯了,並且前面已經經歷過一次錯誤情報,於是後面改成正確的。乙在第5局傳遞關於D的信息

至此,覆蓋了所有情況,甲乙兩人無論如何都能取得勝利了!

———————————————12月10日更新———————————————

最近看了知乎和貼吧幾位大神的解法深受啟發,於是想要研究一個通法,來求解出n勝m的策略。

想來想去沒有別的辦法,乾脆就枚舉吧。

於是寫了個小程序,演算法核心思想大致如下:

枚舉每一種策略,判斷是否可行(甲能否根據乙丙之前的局面來找到自己本局應該出什麼)

並且還要保證勝局符合要求。一旦枚舉到符合要求的答案,立即終止並輸出。全部枚舉完還沒找到答案則輸出無解。

理論上講可以算出來任何n勝m的策略,但由於本人不太會優化...最終時間複雜度為

O(n^2*2^n*4^(n*2^n)),空間複雜度O(2^n)。這是非常可怕的級別....

對於n&<=2的情況可以秒出答案,n=3,m=0時也秒出,n=3 m=1時花費30秒左右,m=2就不知道要幾年了,n&>3估計算到宇宙窮盡都解不出來。

如果大神能想到優化的方案不妨討論討論


甲乙遊戲前討論,如果乙看見後面答案是1居多,則第一題答乙1甲後面完全模仿,如果是0居多則乙答0甲乙後面完全模仿。

或者乙答的跟電腦相同,表示後面X輪是0、1切換,回答根電腦相反表示後面三個以上數字連續為1或者0…

我腦袋不好使,還有點懶,只能想到這麼多了…估計大體思路是這樣吧…

說實話,這讓我想起了很多年前在某科普節目上看到的一個挺有意思的題。

首先找ABCD四個人

紅A 紅B 藍C | D藍

每個人在後腦勺貼上一個標籤,寫上紅或者藍,並被告知,只有紅藍兩色,每色兩個。(看上一段)其中「|」為一面不透明的牆,也就是說D什麼也看不見,然後ABC面對著牆,排成一線。其中A可以看見B和C後面的字條,B可以看見C頭上的紙條。

問題是讓每個人猜自己頭上的寫的應該是什麼字,不可以瞎猜,必須要有足夠的理由證明。

最後,派一個人每十分鐘挨個人問一次,答不出來,或者沒有足夠的理由證明,就會被澆一桶冷水…(據說讓大腦降溫會讓人理清思路…這什麼鬼…)

反正最後結果是沒有一個人能答出來…

(我覺得是被冷水嚇的…)

當時我才十一二歲,無論怎麼想都想不出來答案,最後公布答案的時候才發現,原來是這麼簡單…同時給了我很深的印象,所以直到十年後的現在,我都記得…


看到這問題第一反應就是拔電線。


把電源拔了,再揍一頓,想不贏都難。

前提是

那兩個人能把一個人揍趴下


吳澤輝的答案一般化以後 對於x局 應該最多可以保證 round( (X-1)*2/3) ) 個勝局


推薦閱讀:

想做一款能引導人們積極向上的遊戲,要具備哪些能力?該從什麼做起?
2017 年,全球遊戲圈有哪些值得回顧的新聞?
日本任天堂在1983年和FC一起推出的權利金制度是怎樣的一個制度?
你心目中的「最佳遊戲年」是哪一年?

TAG:遊戲 | 數學 | 邏輯 | 計算機科學 | 密碼學 |