這道組合題有哪些好的方法？

1樓：

@陳世騰的方案可以稍加改進w

我們的方針顯然是找到 1 個說真話的壬, 然後讓真壬把剩下壬的身份招供出來, 後者至多需要步是當然的.

那麼找到真壬只需執行如下次詢問之手續:

隨機找 1 個壬, 置棧頂.

2. 抽 1 個還未詢問過的非棧壬，問棧頂壬, 其是何壬

2.a.若回答新壬是真壬，新壬入棧

2.b.若回答"哈哈, 你神必壬", 那麼姑且二壬皆沙之

其正確性由以下觀察保證: 每次被沙之壬都至多有 1 個真壬, 至少有 1 個神必壬. 再由真壬數量佔優知倖存壬 1 定都是真壬.

仍可稍加改進. 僅剩 1 個非棧壬時, 棧頂為空則其壬必真壬; 否則棧頂壬必真壬. 這須次詢問. 並且當為偶數時可以先沙任意 1 壬, 這須次詢問.

似乎不能詢問更少次數了, 不然從詢問的壬的數量裡收集不到足夠的資訊來識別真壬……

2樓：陳世騰

精確值還沒想到怎麼算，但是我能大概給個上下界估計。假設需要問的最優問題數是m。

首先，我們用A表示只說真話的人的集合，B表示可以說假話的人的集合吧。那麼對A的限制只有 n/2" eeimg="1"/>，因此A有大約種不同的取法。而問m個問題，每個問題只有AB兩種回答，所以總共有種不同的回答。

要通過這種不同的回答區分種不同的情況，需要。

然後我們設計乙個區分的演算法。首先明確一點，我們只要找到乙個A中的人，然後問他其他人的身份，我們就能得到所有人的資訊。下面我們就想辦法找出乙個A中的人。

我們注意到，如果問某個人另乙個人的身份，得到回答是B的話，這兩人中至少有乙個是B；如果問兩人對方的身份，回答都是A的話，這兩人身份相同。於是我們把n個人分成兩兩一組，如果n是奇數的話有一人自己一組，共組。問每組兩人對方的身份。

如果回答有B的話，說明這組中有B，因此剩下的人中A一定還是多數，因此可以移除這一組。餘下的每組都是回答對方是A的（以及可能有一組只有1人），每組的人身份相同。由於餘下的人中A占多數，因此A的組數也更多。

這樣的話每組任意取乙個代表，把餘下的人移除，剩下的這一群人中，A還是占多數。這樣，我們就通過問個問題，把人減少到至多。然後遞迴的處理餘下的人。

當人數降低到1的時候，我們就找到了乙個A，這過程需要問至多個問題。然後再問這個A其他人的身份。至多3n次提問解決問題。

所以。不知道能不能做得更好。