囚徒帽子
Prisoner's Hat
题目详情
100 名囚徒排成一列面向同一方向，每人随机戴一顶红帽或蓝帽。每个囚徒只能看到自己前方人的帽子，看不到自己和身后人的。
从队尾开始依次向前，每个人只能说一个词："red" 或 "blue"。说对自己帽子颜色就获释，说错就继续关押。所有人都能听到前面/后面人的回答，但听不到是否答对。
问：在最佳策略下，最多能保证释放多少人？
提示：队尾可以统计并传递某种“奇偶信息”。
One hundred prisoners are lined up, facing one direction and assigned a random hat, either red or blue. Each prisoner can see the hats in front of them but not behind. Starting with the prisoner at the back of the line and moving forward, they must each, in turn, say only one word which must be "red" or "blue". If the word matches their hat color they are released, if not, they are kept imprisoned. They can hear each others' answers, no matter how far they are on the line, but they do not hear the verdict (whether the answer was correct). A friendly guard warns them one night before, giving them enough time to come up with a strategy. How many prisoners can be freed using the best strategy?
Assume that there is an unknown number of red & blue hats.
Hint
The prisoner at the back can count the number of each color and convey some information to the next.
解析
可以保证释放 99 人；队尾那 1 人只有 50% 的概率获释。
策略：约定“红帽数量的奇偶性”。
- 队尾（第 100 人）观察前方 99 顶帽子中红帽的数量：若为偶数就喊 "red"，若为奇数就喊 "blue"（用喊的颜色编码奇偶）。
- 第 99 人看见前方 98 顶帽子并听到第 100 人的编码，就能推出自己帽子的颜色，使得“前方红帽数 + 自己红帽”与编码匹配。
- 之后每个人都把已经确定的人的帽色计入，继续保持同一奇偶约束，从而依次推断自己的帽色。
因此除了第 100 人外，其余 99 人都能确定自己帽色。
Original Explanation
99 of the 100 prisoners can be freed, and 1 has a 50:50 chance of freedom.
Solution
We can number prisoners from 100 to 1, with 100 being the last person in the line. Prisoners agree that if the person will say "red" if there are an even number of "red" hats visible on the prisoners 1 to 99, and blue otherwise. This way, prisoner number 99 can look ahead and count the red hats. if they add up to an even number and the number 100 said “red”, then 99 must be wearing a blue hat. if they add up to an even number and number 100 said “blue”, signaling an odd number of red hats, number 99 must also be wearing a red hat.
Similarly, number 98 knows that 99 said the correct hat, and so uses that information along with the 97 hats in the front to figure out their own hat's color. This can continue till the first prisoner.
This strategy will free 99 prisoners. But the prisoner has to rely on luck and has a 50:50 chance of being right.
Notes:
-
If a prisoner decides to give an incorrect answer on purpose, then all the successive prisoners end up giving an incorrect answer. Unless there is another corrupt prisoner who inverts the parity.
-
In an alternative universe, the friendly guard informs the prisoners that both colors are even. All one hundred prisoners can be freed.