TOAD 27 - Another Hat Problem

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

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\) 个人猜对。