题目
这次有\(n\)名囚犯，每个人会被随机戴上一顶红帽或黑帽（公平抛硬币决定）。
囚犯排成一列，每个人只能看到自己前方所有人的帽子，看不到自己的帽子。
他们从队尾到队首依次报出自己帽子的颜色，猜错者会被处决（是否猜对不会当场告知，处决在最后统一执行）。
具体地，队列中第\(i\)个人能看到\(1,2,\dots,i-1\)号的帽子，并能听到\(n,n-1,\dots,i+1\)号已经报出的答案。
囚犯可在游戏前共同制定策略，目标是在最坏情况下保证尽可能多的人存活。
问：最坏情况下最多能保证多少名囚犯存活？
分析
答案是：最坏情况下最多保证\(n-1\)人存活。
先给出可行策略（下界）：
- 约定“红帽数奇偶校验”规则。把红帽记为\(1\)，黑帽记为\(0\)。
- 最后一个发言的人（队尾）先看见前面\(n-1\)人的帽子，计算其中红帽数的奇偶性。
- 若他看到的红帽数为偶数，就报“黑”；为奇数就报“红”。这句话不一定是他自己的真实帽色，但它把“前面\(n-1\)人红帽总数是偶还是奇”这个1比特信息传给后面所有人。
- 之后第\(i\)个人发言时（\(i<n\)），他知道：
- 前面人的帽色（看得到）；
- 后面已发言者中，除队尾外，其余人都可视为已经报出真实帽色；
- 队尾给出的总奇偶信息。
因此第\(i\)个人可以唯一推出自己的帽色，并保证自己猜对。
所以除队尾第一位外，其余\(n-1\)人都能保证正确。
再证最优性（上界）：
- 队尾第一位在发言时，看不到自己的帽子，也没有任何先前发言可参考。
- 对他而言，存在两种仅“他自己帽色不同”的情形，而他接收到的信息完全相同，因此他的发言在这两种情形下必须一样。
- 于是这两种情形中至少有一种会使他猜错。
所以不可能保证\(n\)人全活，最多只能保证\(n-1\)人。
综上，最坏情况下可保证的最大存活人数为\(n-1\)。