最大团问题

lsr314 · 发表于 2016-4-7 10:16:35

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

某校一年级有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).

lsr314 · 发表于 2016-4-8 13:12:14

太难的话，先求E(3)=？

一个人的树枝 · 发表于 2016-4-8 15:46:37

看着这问题就挺有意思的，我想解答，但是都忘得差不对多了，回来看看你们的解答，顺便给你们加加油。

whbns · 发表于 2016-4-15 08:58:50

如果一个人在第三年加入另一个班的圈子，那需要在后两年里和那个班里所有人都同班过。由于分班是随机的，这个概率会非常低。所以虽然E(3)大于25，它应该会很接近25。
目测E(6)都到不了26。

whbns · 发表于 2016-4-15 09:51:27

试了一下，到后面找最大团太慢了，所以只运行了很少的次数。
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
后面太慢了就没等了。

lsr314 · 发表于 2016-4-15 11:23:04

whbns 发表于 2016-4-15 09:51
试了一下，到后面找最大团太慢了，所以只运行了很少的次数。
3年的100次全是25
4年的50次1个26其他都是25 ...

增长如此缓慢的话，我倒是很想知道大约第几年期望值能达到50.（理想状态下，不考虑毕业等影响）
如果100人计算量太大的话，可以考虑减少人数，比如20个人分成4个班，或者15人分成3个班。

whbns · 发表于 2016-4-15 11:30:30

lsr314 发表于 2016-4-15 11:23
增长如此缓慢的话，我倒是很想知道大约第几年期望值能达到50.（理想状态下，不考虑毕业等影响）
如果100 ...

其实也不是很缓慢了，6年接近26，7年已经差不多27了。后面其实可能会涨得快一些，不过跑不出来了。。。

whbns · 发表于 2016-4-15 12:47:50

20个人分4个班的结果是这样的，每种年数运行了100次。

result.zip (1.58 KB, 下载次数: 2)

lsr314 · 发表于 2016-4-15 14:10:49

第12年均值就接近49了，中间这几年均值的增长基本上是线性的，估计第24年左右最大团人数就接近总人数了，这个时间长度100人和20人差不多。

whbns · 发表于 2016-4-15 20:38:05

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的时候才能跑出来。。。

账号		自动登录	找回密码
密码			欢迎注册

[提问] 最大团问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

评分

点评

点评

点评