一个国王抓住了100个犯人。一天他决定把他们都处死

那也有可能正好是那个没编的号啊，还不是没用。。。

3# chineseginger
犯人间应该不允许交谈吧，允许的话直接告诉对方他的号码就得了。
所以这个从大到小排列算不算交谈的一种呢，起码算一种沟通了。我想之前犯人都知道从大到小排列的，那五个5号的中间三个人，看到前面是5号，后面是5号，应该知道自己就是5号。

深奥啊
求解

不知道不能传递任何信息具体指什么，但如果可以犯人走动的话，这题目是可以解的
简化一下题目，4个人。

先讨论策略，选定3个人，（0）号（1）号和（2）号。0号作为基准人，发完号就站定不动。（3）站在（0）左边，表示加，右边表示减。由（2）号判断是否与（1）号相等，如果相等就站在2人前面，小于1号站左边，并走（1）-（0）-（3）=X步。这样1号只要用（0）+（3）+X就能得出自己的数字了。同理，大于站右边并走Y步。

人数多时，走的步速过多的话，从5号开始可以继续进行站队，若小于站右边，大于站左边，多次重复，很快就能得到10以内的步数了吧。

自己写完了感觉也不对的样子 因为这样的走的话基本算作弊了吧

另外19楼所说的可以传递数字的话。只要上来选一个人做基准人，大家都写他的号码好了。传到他手上他知道自己号码是什么，写了就WIN了。这个根本不存在什么策略了吧。也不符合题意了

不能进行任何意义上的传递信息的话。
自己的帽子数字和其他人的数字是相互独立。貌似无优势策略啊。只能大家都选一个数字呢，譬如88，这么吉利的数字，国王比较喜欢吧，总不能一个不出现吧。哈哈

如果没有信息传递，此题的最优策略就是任意解，即数字随便写即可
因为每个人的号数独立于其他人的号数，看到别人的号也不会影响自己头上的号
那就是看人数
只有一个人
给你一个号 1-100
你猜对就行
不过这是100人
全军覆没的机会是0.99的一百次方
当然，人数越多，就越容易成功
也就是概率上的当重复试验的次数无穷多的时候
小概率事件也会是必然事件

每一个犯人把其余99个人的数字记下来再除以99，然后在纸上写上这个数字。

不能交流，排队本身就是交流（设定这个我还真不如设定把重复号码的人排在一起，这样不就搞定了）
对于这种概率独立的事件，别人帽子上的数和我帽子上的数并不相关
我怀疑题目条件没给全，目前来看不用任何策略和用策略导致最终逃生的概率都是一样的
1-0.99^100 大概 64%左右

sleight 发表于 2011-2-9 22:04
假设所有人头上数字之和为S，第n个人看到的数之和为S（-n），其头上的数为S（n）
则S（n）=S-S（-n）
mod100 取余数式子依然成立，-S（-n）对100的余数各人可知，S对100的余数只能从0到99，编号0到99取值，肯定有一人能得到正确的S值，从而由观察到的S（-n）求得S（n）

sleight的想法很赞，方法可能没表述清楚，我来解释一下~

假设第n个人头上数字为A(n)，令 S = A(1)+A(2)+...+A(100) mod 100（除以100的余数）;
犯人协商后，让第n个人报B(n)（后面解释），令 S(n) =A(1) +...+A(n-1)+B(n)+A(n+1) ...+A(100)  mod 100 ;
假如我们令S(1)=0,...,S(100)=99，那么存在S(i)使得S(i)=S, 于是A(i)=B(i), 即第i个犯人报对头上的数，犯人们得救；
从而犯人们只要约定第i个犯人报i 减去他看到其他人头上的数字之和除以100的余数，即B(i)= i- [A(1) +...+A(n-1)+A(n+1) ...+A(100)]，便可以使大家都获救。

p.s.这个问题关键是找一个不变量，即所有人头上数字之和为S~等下出去看娜娜Vs巴萨的比赛，无聊水一下~

“一个国王抓住了100个犯人。一天他决定把他们都处死。但是在处死之前，国王把他们召集起来，想给他们最后一次机会。他说将会给每个人一顶帽子戴在头上。每顶帽子上随机写上1到100之间的一个数，作为编号，但允许重复。同时，每个犯人都可以看到其他人帽子的编号，但看不到自己的。每个人会得到一张纸条，犯人自己在上面写下一个数。如果有一个犯人写下的数字和自己帽子的编号相同，所有的犯人都将被释放，否则所有人都将被杀掉。在国王给帽子编号之前，犯人们将有十分钟的时间来讨论策略，在国王正式给帽子编号以后就不许再说话或者传递任何信息。这个策略将会是什么呢？”

对于任意一名犯人i, 他的帽子上数字集合 S={1,2,...，100)
"每顶帽子上随机写上1到100之间的一个数，作为编号，但允许重复。"


题目上说随机，所以假设1到100之间概率相等
p(si)=1/100


两名犯人帽子上数字相同几率为 1/100 乘以 1/100 = 1/10000
所以犯人i, 和其他99个犯人帽子上相同数字的几率是 1/10000 times 99 小于 1/100
所以他和其他犯人帽子上数字不同的几率是大于 99/100

犯人i 选择任意和其他人犯人帽子上数字不同的一个数字
可以计算出他写的数字和他帽子上数字相符合的概率，如果这个概率乘100大于1，那么这个方法将在统计学上保证这些犯人最终被释放.
具体算法：
i 以外的99名犯人中帽子上数字重复的人数为n
n     n的概率                           写出数字和帽子上数字复合概率（因为我们假设i帽子上数字和其他人不同这个概率为0.99所以最后要乘上0.99)
0     0.99^99                                             1 x0.99
1     0.99^98x0.01                                    1/2 x0.99
2     0.99^97x0.01^2                                1/3 x0.99
3     0.99^96x0.01^3                                1/4 x0.99
..     ...                                                        ...
99     0.01^99                                           1/99 x0.99


求和得出
他写的数字和他帽子上数字相符合的概率> 1/3
任意一个犯人写对的几率大于 1/3, 100个犯人用这个方法概率上逃生的可能性大于3000%


解决方案：每名犯人写出任意一个和其他犯人帽子上数字不同的数字。

50# christina3123

"所以他和其他犯人帽子上数字不同的几率是大于 99/100"这个有问题，应该是100!*(1/100)^100