彩虹帽子

Rainbow Hats

专题: Brainteaser / 脑筋急转弯
难度: L4
来源: QuantQuestion

题目详情

7 名囚徒各戴 7 种颜色之一的帽子（例如彩虹七色），每人能看到其他 6 人的帽色但看不到自己的。

之后所有人同时猜自己帽色（每人说一个颜色），所有人都能听到他人猜测。

如果至少 1 人猜对，则全部获释，否则全部处死。

请给出一种策略，保证他们必然获释。

Seven prisoners each receive a hat of one of seven colors (e.g., the colors of the rainbow). They see each other’s hats but not their own, and cannot communicate once they see them. Each prisoner guesses his own hat color (all guesses heard by everyone). If at least one prisoner guesses correctly, all go free. Otherwise, all die. Devise a strategy that guarantees their freedom.

解析

把 7 种颜色编码为 $0\sim6$ （模 7）。给囚徒编号 $0\sim6$ 。

设全体帽色编码之和为 $S\pmod 7$ 。

第 $i$ 个囚徒看到其他 6 人编码和为 $T_i$ ，则他猜自己的编码为

(S-T_i)\bmod 7.

等价地，让囚徒 $i$ 假设总和为 $i$ （模 7）并据此猜测，则恰有 $i\equiv S$ 的那个人猜对，从而保证至少 1 人正确。

Original Explanation

Assign each color a number 0–6 mod 7, and label prisoners 0–6. Let the sum of all hats’ “color numbers” be $S$ (mod 7). Prisoner $i$ guesses the color that makes $(i + \sum_{\text{other }6} \text{visible colors}) \bmod 7 = S.$ Only the correct $i$ (namely $i \equiv S \pmod{7}$ ) will guess his hat color correctly, ensuring at least one correct guess.