(一)
要問3個朋友中有幾個人今天是愚人節,則有4種可能的答案:0,1,2,3個
既然有4種答案 則表示最少要問2個是非題 (第一題有兩種回答*第二題有兩種回答=4種結果)
也就是說,每一種問題的回答都要刪掉兩種可能
於是可以問A以下這兩個問題
「如果我問你『三人中今天是愚人節的人數
至少兩人嗎?』你會回答 是 嗎?」
「如果我問你『三人中今天是愚人節的人數
是奇數個嗎?』你會回答 是 嗎?」
不論A說真話或假話,他回答出來的一定是雙引號內正確的答案。
於是可以做出回答和人數的對照
(是,是) --> 3人
(是,否) --> 2人
(否,是) --> 1人
(否,否) --> 0人
(二)
其實如果秉持著第一題的原則
不難發現每次問題都可以刪掉一半的可能 於是知道等一下可能會需要用到log(以2為底)
回到第二題,如果有N個人,那麼答案就會有N+1種可能(0,1,2,...,N)
但是要注意 如果令N+1=2
k (k是正整數)
那麼2
k-1和2
k問的次數會一樣(都是k);2
k+1則需要多問一次(k+1)
所以,待會在用高斯符號前需要讓(N+1)先-1
才能2k-1和2k取log和高斯後所得到的值一樣
最後再把當初扣掉的1加回來即可
於是變成
-1)%5D+1)
化簡得
