Question

号称是美国高考的题：100个囚犯，国王准备赦免他们的机会，准备100顶红蓝帽子那啥的问题。求指教。。

问题全部：有一个监狱，关押着100个死囚，这天国王心情好大赦，让死囚有一次活的机会，准备了100顶帽子，分红，蓝两色（红，蓝具体数量未知，只知总和100）现让死囚每人戴顶帽子（死囚不知道自己戴什么颜色的帽子 ），国王让死囚排成一列（最后一个能看到前面99个人帽子颜色，但看不到自己，倒数第二个死囚能看到前面98人的颜色，但后面看不到，以此类推 ），现国王要求从最后一个开始报自己头顶上帽子的颜色，报对就能活着，报错就要枪毙，现请你设计方案设法让尽可能多的人活下来，请问最多能保证多少人活着？要求设计方案

看过这个问题，然后看过很多人给出的答案，绝大部分人会咬定会死50个人，活50个人，或者只死最后一个，前面99个不死。我真搞不明白他们怎么推理出来的，有点不可思议。。。要是貌似颜色是7:3, 你也要死50个？你这个死亡比例大了去了啊！要是只用死一个，我求你给我解释下用什么方法可以达到这么高的存活率。。。

我自己给出了一个方法：

方法一： 后一个人报前一个人的帽子的颜色
-------------------------------------------------------------------------------------------
第100号人报前一个人的颜色，如果自己活了，那么100号运气好，自己也对了。那么99号也活了，99号就报后面那个人给的信息就可以了。
若100号死了，同样的，99号也知道自己帽子的信息了，所以99号活了。

那么98号和97号也一样，重复以上活动。按照归类法推下去，比如有30顶异色的帽子。那么就只有30组的人会配成异色队。这个异色队就只用死30个，活30个。

剩下的全是同色队的了，都死不了。

这个方法死得人可能是红色的一部分，也可能是绿色的一部分，但是绝对不会死得超过比例小得那部分。比如7:3，死得绝对是3， 2:8，死的绝对是2. 5:5,死得就是5，红蓝比例可以任意。死亡的对红，蓝方比较公平。

方法二：所有人报帽子颜色比例大的颜色。
-------------------------------------------------------------------------------------------
第100个人可以看到前面99个人的颜色比例，看哪个颜色的比例大就报哪个颜色。
第99个人可以看到前面98个人的颜色比例，外加后面一个人给的信息，归纳出哪个颜色比例大。

或者，前面99个听到第100个喊什么颜色，前面的就喊什么颜色就可以了。。。

死得人也是比例上小的这一部分人。只是，死得人会是纯色的帽子。似乎对囚犯不是太公平。。。因为他们的命运从拿到帽子那一刻就决定了。。。

---------------------------------------------------------------------------

以上，求达人点评

Answer 1

这题两年前在班里就做过了，最高存活率能达到99.5%，就是最后一个人50%的几率存活，前面的99个人保证能存活。首先，这100人先有一个约定，最后一个人能够看到前面的99顶帽子的颜色，而必然数量是一奇一偶，最后一个人说出奇数个帽子的那个颜色，于是那个人的生命就听天了。假设前面99个人中有奇数个红帽子，那么倒数第二个人听到最后一个人说红色时，就明白了前面99人中有奇数个红帽子，他就可以数自己前面的98人有多少个红帽子，如果结果还是奇数，说明自己是蓝帽子，而如果结果是偶数个，那么自己就一定是红帽子，以此类推，前面的99人都能够确定自己的颜色，所以就有99%的生存率，而站在最后的那个人不知道自己是什么颜色，所以有50%的生存率，那么总共100人固然就有99.5%的生存率了。

Answer 2

其实因为事先不知道分别多少，然后囚犯不可能有商量的余地，不然这题太简单了。所以只能假设每个囚犯智商都不低，能想到一块去，但是不可能打暗示与商量，那么第一个看到了22红，77蓝。对他来说有可能蓝色78，也有可能红色23，如果他错了，那么他的颜色所有人都能确认（之前我说了假设蓝色78）然后第二人有两种颜色可能，红色的话他眼里就是21红77蓝，因为知道了最后一人蓝色，他也知道一共21红78蓝，然后不管正确与否，所有活着的都知道他是红色，也就是说前方蓝色，就能感觉77蓝22红，前方红色能感觉78蓝21红如果第三人答完，那么其实大家都能推断出22红78蓝了。因为你们想啊，始终在22、77；以及21、78之间波动，没有出现过79蓝，没有出现过23红，那么颜色分别多少就推断出来了，所以第三人开始后面幸存大大提高，理论上第四人开始就无伤亡了

Answer 3

若只能说“红”或者“蓝”两个字的话，想了半天，最好的办法就是你的方案一了（也许还有更好的，但实在想不出）。用你的方案一的话，死的人会比最小比例小一些。因为若蓝色是最小比例，有30个，那最多有30组异色，就是死30人。而实际情况，会出现两个蓝色一起的情况，所以死的人数会比最小比例小。
若不限于红蓝两个字，只考虑是否说真话的话。有一个办法可以至多死一个。就是最后一个报前一个帽子颜色，最后一个可能死，也可能活。但前面一个知道自己的帽子颜色了。接着他再看前面一个的帽子颜色。若和自己的一样，比如都是红色，就直接说红色，若和自己不一样，是蓝色，就说自己的帽子不是蓝色。这样最多就死最后一个人了。

Answer 4

用奇数跟偶数来解决，第100个囚犯报出前面99顶帽子其中的奇数或偶数是什么颜色就行，后面的囚犯就能根据前一个囚犯的帽子颜色和观察到的帽子颜色知道自己的帽子颜色了。举例让第100个囚犯报奇数的帽子颜色，假设报了红色，蓝色就为偶数，第99个囚犯观察前98个帽子红蓝为偶数自己戴的就是红色，红蓝为奇数自己戴的就是蓝色，第98个囚犯根据第99个囚犯报的帽子颜色得知前98个帽子颜色的红蓝为双奇数或双偶数，在根据98号囚犯看到的前97个帽子颜色的奇偶数得知自己帽子的颜色，97号知道99顶帽子颜色的奇偶数，减去99号跟98号的，再观察前面96顶帽子颜色得知自己的，以此类推。最少能活下来99个囚犯，第100个囚犯看运气

Answer 5

对比奇数偶数 数一下就可以了 最后一人说绿的话就是前方有偶数个绿色帽子 前面所有人都要听得到 然后心里做减法就行了 存活率99.5%