最大团问题
某校一年级有100个学生，每年九月，学校都将他们重新打乱，划分成4个班，每个班25人，划分的方式是抽签，可以看成是完全随机的。假设没有学生增加或者流失的情况。第n年结束后，如果一些人彼此都曾经同过班，那么我们称他们构成一个圈子，人数最多的圈子中的人数记为G(n)。问G(n)的期望值E(n)是多少？目前只能确定E(1)=25,E(2)=25,E(3)>25,E(n)<100.希望可以求出E(6)以及E(9). 太难的话，先求E(3)=？ 看着这问题就挺有意思的，我想解答，但是都忘得差不对多了，回来看看你们的解答，顺便给你们加加油。:b: 如果一个人在第三年加入另一个班的圈子，那需要在后两年里和那个班里所有人都同班过。由于分班是随机的，这个概率会非常低。所以虽然E(3)大于25，它应该会很接近25。
目测E(6)都到不了26。 试了一下，到后面找最大团太慢了，所以只运行了很少的次数。
3年的100次全是25
4年的50次1个26其他都是25
5年的50次4个26其他都是25
6年的10次：26 26 26 25 25 26 26 26 26 25
7年的5次：27 28 27 27 26
后面太慢了就没等了。 whbns 发表于 2016-4-15 09:51
试了一下，到后面找最大团太慢了，所以只运行了很少的次数。
3年的100次全是25
4年的50次1个26其他都是25 ...
增长如此缓慢的话，我倒是很想知道大约第几年期望值能达到50.（理想状态下，不考虑毕业等影响）
如果100人计算量太大的话，可以考虑减少人数，比如20个人分成4个班，或者15人分成3个班。 lsr314 发表于 2016-4-15 11:23
增长如此缓慢的话，我倒是很想知道大约第几年期望值能达到50.（理想状态下，不考虑毕业等影响）
如果100 ...
其实也不是很缓慢了，6年接近26，7年已经差不多27了。后面其实可能会涨得快一些，不过跑不出来了。。。 20个人分4个班的结果是这样的，每种年数运行了100次。
第12年均值就接近49了，中间这几年均值的增长基本上是线性的，估计第24年左右最大团人数就接近总人数了，这个时间长度100人和20人差不多。 lsr314 发表于 2016-4-15 14:10
第12年均值就接近49了，中间这几年均值的增长基本上是线性的，估计第24年左右最大团人数就接近总人数了，这 ...
24年：95 94 93 94 94 96 94 95 94 97 （平均94.6）
30年：98 100 99 99 99 98 98 99 100 99 （平均98.9）
确实25年左右就接近总人数了。
我用的这算法只有结果接近25或者接近100的时候才能跑出来。。。
页:
[1]
2