回复：挑战：如果帽子的颜色有10种，什么样的算法，可以让被砍头的人最少？

存活的期望值为98.2。

先解释一个期望值为96.4的算法：
把颜色编成1至10号。把10种颜色的奇偶性（奇数为1，偶数为0）组成1个10位的2进制数。这个2进制数对应的10进制数范围是0至1023， 最多4位数。
如：1001100101表示第1，4，５，8，10种颜色为奇数，其余为偶数。
前四个人算出剩余96人中10种颜色的奇偶性组成的2进制数，转换成对应的10进制数，然后分别报出这个4位数每一位对应的颜色，如236，则前四个人分别报第0，2，3，6种颜色。则剩下的96人可以知道他们头上所有颜色的奇偶性。他们根据看到的，以及听到的颜色，可以准确说出自己的颜色。所以期望值为0.1*4+96=96.4。

期望值为98.2的算法是在这个算法上的改进：剩余的人不需要知道这个10进制数的全部4位（不足４位用０补足），只要知道后两位（十位和个位）就够了。因为任意两个后两位相同的四位数，其对应的2进制数都至少有3位不同；也就是说：当一个人根据看到的，以及听到的颜色来判断自己的颜色时，尽管他不知道这个10进制数的前两位，但是有且仅有一个四位数（后两位是公告出的）能让他唯一确定自己的颜色。
举例来说：如果公告的数字是2１。当一个人汇总看到的，以及听到的颜色，得到2进制数：1001100101。同时根据以下所有后两位为2１的10进制数及对应的2进制数：
0021 对应 0000010101
0121 对应 0001111001
0221 对应 0011011101
0321 对应 0101000001
0421 对应 0110100101
0521 对应 1000001001
0621 对应 1001101101
0721 对应 1011010001
0821 对应 1100110101
0921 对应 1110011001
1021 对应 1111111101
他会发现只有0621（1001101101）可以由他汇总得到的2进制数（1001100101）通过转换１位数字得到。所以他可以知道自己一定是７号颜色，且这个10进制数一定是0621。
综上所述，前两个人算出剩余9８人中10种颜色的奇偶性组成的2进制数，转换成对应的10进制数，然后分别报出这个4位数的十位和个位。剩余9８人根据以上算法可以准确说出自己的颜色。所以期望值为0.1*２+98=98.2。

所有跟帖： 

• you beat me -guest007- ♀ (0 bytes) () 02/18/2010 postreply 00:51:14

• 我不同意第二步 -guest007- ♀ (591 bytes) () 02/18/2010 postreply 05:34:49

• 回复：我不同意第二步 -wxczcbm- ♂ (226 bytes) () 02/18/2010 postreply 19:48:22

• Now 我同意第二步 and I add my 第3步 to reach 99.1% -guest007- ♀ (848 bytes) () 02/19/2010 postreply 10:11:27

• 呵呵，我不同意第三步。 -wxczcbm- ♂ (470 bytes) () 02/19/2010 postreply 21:18:23

• Yeah, u r Right. .... 10^1 is actually =10 not 1 -guest007- ♀ (53 bytes) () 02/20/2010 postreply 06:38:29