回複：挑戰：如果帽子的顏色有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