: 他手上有黑桃A~K，共13張牌。他從中選出一張牌，要我猜出那張牌是什麼牌。他說我可以
: 問他3個問題，他會回答YES或NO!
: 而這3個問題，他其中一個會說謊。(另外兩個會誠實回答)

板友證明了用二元問法6次解不開13張

我剛研究出了6次解13張的方法,當然這要用一點小技巧

不過解的過程要應回答而靈機應變,煩瑣的部分我盡量簡化


簡單作弊法:

問  你這一次要回答NO對不對?
此時他不論回答yes 或no都將說謊,然後解決

這問題再問一次則回答將頭腦爆炸,我們只要解題就好了
後面不用這種技倆


首先一般問法還是把數字分2堆,回答說正解所在那邊為Y,另一邊則給N

當有一個數字得到2個N之後就可以把它淘汰掉了(至少給它N的其一是實話)

接下來我會用表示法

13V 0N Q6  表示還有13個數字沒淘汰掉,0個數字給過N,還可以問6次問題


介紹雙方策略:

問方:1.盡量製造每個數字都有N,因為這樣就表示前面回答已有說謊,不然就沒答案了
        此時只要 2的Q次方不小於V就行,一般的二元問就行了,後面當作已知

     2.其次盡量製造越多N越好,這樣才容易淘汰掉數字

綜合上面2項,當分2堆數字不同量時,把沒N的數字放到少的那一邊,這樣至少符合一項策略


答方:1.和上面問方策略作對

     2.盡量讓之前全部是實話時,留下更多沒N的數字


先證明3V 2N Q2可解，之後此狀況或更佳當做已知可解
一般3V Q2是不能解的,但是只要有2N就行

例如剩下1,2,3   其中2,3有N

3V 2N Q2     N:2,3    Y:1
問 1~2     3
答  Y      N
***
答  N      Y
2V 2N Q1  已說謊,最後一問解
***

2V 1N Q1    N:2  Y:1
問:1+1=2對不對?

用一個完全無關的問題把最後一問消耗掉!
若現在說謊表示之前沒N的為正解
若說實話,則之前說謊,正解為那1N


遊戲開始

第一回合
13V 0N Q6
問 1~6      7~13
答  N        Y
顯然要回答在多的那一堆

第二回合
13V 6N Q5      N:1~6
問 1~7      8~13
答  Y        N
***
答  N        Y   的話會立即淘汰1~6,變成
7V 1N Q4    N:7   Y:8~13
問 7~9     10~13
答  Y        N   3V 2N Q3已知解
答  N        Y   5V 5N Q3已知解
***

第三回合
13V 12N Q4    N:1~6 8~13  Y:7
問 2~7     1,8~13     讓沒有N的7進入少的那堆是關鍵
答  Y        N  (這裡全淘汰掉了)
***
答  N        Y   全都有N了,淘汰2~6
8V 8N Q3    N:1,7~13
已經說謊,剛好2的3次方是8解決
***

第四回合
6V 5N Q3    N:2~6   Y:7
問 2~4    5~7
答  Y      N   淘汰5,6
4V 4N Q2 已知解
***
答  N      Y   淘汰2~4
3V 2N Q2 已知解
***

恭喜破關!
※ 編輯: kohttp          來自: 210.68.38.81         (10/27 10:41)