好人隊長和壞人隊長

來自專欄 ⑥的完美算數教室

在諸多智力題里，有關『黑帽子和白帽子』的有茫茫多，很多都爛大街了所以我一直沒有收錄到專欄里。不過，下面這道我確實沒怎麼見到過：

在這個題目里，有251個壞人和251個好人。遊戲開始時，壞人先在一個屋子裡站成一排，每個人左手一頂黑帽子，右手一頂白帽子。確定好了壞人的順序（排列）之後就不能再變了。

然後，好人將逐一進入屋子。在每個好人進屋之前，壞人群體將選出一個還沒戴帽子的壞人。好人進屋之後，『被選中的壞人』會對進來的好人揮手，而這個好人可以決定這個壞人到底是戴上左手的黑帽子，還是右手的白帽子。決定完之後，好人離開現場，不得再與其他任何人交流。

當250個好人經過了這個過程之後，屋子裡還剩下1個壞人沒有戴帽子，我們稱之為『壞人隊長』。此時，壞人隊長可以自由地選取黑帽子或白帽子戴上。隨後，場上唯一剩下的好人，我們稱之為『好人隊長』，進入屋子。好人隊長的目標，也就是好人群體的最終目的，是要選擇若干個壞人（一個壞人子集），並且要求壞人隊長必須在這若干個壞人之內。

在整個遊戲開始之前，好人們和壞人們都可以商議一些策略。問：好人用什麼策略，才能讓最後好人隊長划出的『一定包含壞人隊長的集合』最小。

來源：@高天 去年在他的程序員交友群里給出了此題。不過版權也不是他的，是CMU的一道題。

（老樣子，答案可能一周後發，也可能評論區置頂。）