0%

TOAD-puzzle-27

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

problem

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

solution

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

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

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