又在军训的时候想出一道题……

Problem

有 $2n$ 个人，编号 1 到 $2n$ ，每个人头上有一顶帽子，帽子要么是黑色的要么是白色的。现在这 $2n$ 个人需要同时说出自己帽子的颜色，如果不少于 $n$ 个人说对了自己帽子的颜色，则这局游戏获胜，否则失败。求是否存在必胜策略。

Solution

其实只要注意到 $n = 1$ 的情况就好了。如果 $n = 1$ 有解，那么把人两两配对，每对至少有一个人说对，则至少有 $n$ 个人说对。如果 $n = 1$ 无解，那就无解了……

对于两个人帽子颜色的相对关系，只有两种可能：相同、不同。于是 A 说 B 帽子的颜色，B 说 A 帽子颜色的反色，有且仅有一个人说对帽子的颜色。

给的题解是另一种方法，推广性更强。我们把这 $2n$ 个人分成两组，每组 $n$ 个人，第 $i$ 组的人假设黑帽子的数目是 $i \bmod{2}$ 。这样有且仅有一组的假设是对的，而且这组里的所有人都会猜对，所以一定恰好 $n$ 个人猜对。