100 囚徒帽子
Prisoner Problem
题目详情
有 100 名囚徒，每人戴红帽或蓝帽。每人能看到其他人的帽子但看不到自己的。
当被点名时，每人必须猜自己帽子颜色。猜对获释，猜错处决。
所有人的猜测与结果公开。
问：是否存在策略保证至少 99 人猜对？
There are 100 prisoners, each wearing either a red or blue hat. Each prisoner can see everyone else’s hat color but not his own, and cannot communicate except for making a guess about his own hat color when called. If he guesses correctly, he is set free; otherwise, he is executed. The guesses and outcomes are public. Is there a strategy that guarantees at least 99 of them will be correct?
解析
存在。
约定“红帽数量的奇偶性”。第一个人用自己的回答来传递前方红帽数的奇偶（他本人有 50% 概率对/错）。
之后每个人根据自己看到的红帽数与已知奇偶信息，扣除之前已经确定的人的帽色，就能推出自己的帽色，从而保证其余 99 人都确定无误。
Original Explanation
Yes. They use parity (mod 2). The first person (prisoner) announces a color corresponding to the parity of the number of red hats (for example). That person has a 50% chance individually, but this conveys a mod-2 sum of the hats to the others. Each subsequent prisoner counts the visible hats, compares to the declared parity, and deduces his own hat color. In total, exactly 1 prisoner might be at risk; the other 99 can be sure.