囚徒帽子（多颜色）
Prisoner's Hat (multicolor)
题目详情
100 名囚徒排成一列，从后往前依次报出自己帽子颜色。帽子颜色共有 10 种且可区分。
每人只能看到前方人的帽子，能听到所有人报的答案。每人只能说一个颜色词。
说对获释，说错当场处决。问：如何最大化获释人数？
100 prisoners are lined up and assigned a random hat These hats are available in 10 different unique and distinguishable colors. Each prisoner can see the hats in front of him but not behind. Starting with the prisoner in the back of the line and moving forward, they must each, in turn, say only one word which must be the color like "red" or "blue" or "green" etc. If the word matches their hat color they are released, if not, they are killed on the spot. They can hear each others answers, no matter how far they are on the line. What strategy should be used to help release maximum number of prisoners?
Hint
Try prisoner's Hat puzzle first
解析
可保证获释 99 人；最后一人（队尾）只有 的存活概率。
做法：给 10 种颜色编码为 。
- 队尾（第 100 人）把前方 99 顶帽子的编码求和并对 10 取模，报出对应颜色（用来传递“总和模 10”的信息）。
- 之后每个人都能根据：队尾报出的模值、自己看到的前方帽子编码之和、以及已经听到的后方人实际帽色（编码），推出自己帽色编码，使得全体编码和满足该模值。
因此除第 100 人外，其余 99 人都能确定自己帽色。
Original Explanation
Solution
Call the first person in back of row the 100th prisoner. The 10 colours will be given codes from 0 to 9. The 100th prisoner will sum the numbers associated with the 99 colours he sees and will say the colour corresponding to it modulo 10. This is enough for 99th person. All he needs to do now is connect the dots, sum the number of hats he can see, calculate modulo 10, and compare it with what 100th prisoner said. This way all 99 prisoners will be saved, and 100th prisoner dies with probability 9/10.