数学研发论坛

 找回密码
 欢迎注册
查看: 795|回复: 17

[提问] 最大团问题

[复制链接]
发表于 2016-4-7 10:16:35 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
某校一年级有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).
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2016-4-8 13:12:14 | 显示全部楼层
太难的话,先求E(3)=?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-4-8 15:46:37 | 显示全部楼层
看着这问题就挺有意思的,我想解答,但是都忘得差不对多了,回来看看你们的解答,顺便给你们加加油。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-4-15 08:58:50 | 显示全部楼层
如果一个人在第三年加入另一个班的圈子,那需要在后两年里和那个班里所有人都同班过。由于分班是随机的,这个概率会非常低。所以虽然E(3)大于25,它应该会很接近25。
目测E(6)都到不了26。

评分

参与人数 1金币 +20 收起 理由
gxqcn + 20 首贴奖励,欢迎常来。

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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
后面太慢了就没等了。

点评

第11年均值≈44  发表于 2016-4-15 13:55
第10年均值≈39  发表于 2016-4-15 13:50
第9年均值在34和35之间  发表于 2016-4-15 13:35
第8年均值在30和31之间  发表于 2016-4-15 13:31
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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个班。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-4-15 11:30:30 | 显示全部楼层
lsr314 发表于 2016-4-15 11:23
增长如此缓慢的话,我倒是很想知道大约第几年期望值能达到50.(理想状态下,不考虑毕业等影响)
如果100 ...

其实也不是很缓慢了,6年接近26,7年已经差不多27了。后面其实可能会涨得快一些,不过跑不出来了。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-4-15 12:47:50 | 显示全部楼层
20个人分4个班的结果是这样的,每种年数运行了100次。
clique.png
result.zip (1.58 KB, 下载次数: 2)

点评

20人时,第8年最大团人数就已经达到总人数的一半了  发表于 2016-4-15 13:15
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2016-4-15 14:10:49 | 显示全部楼层
第12年均值就接近49了,中间这几年均值的增长基本上是线性的,估计第24年左右最大团人数就接近总人数了,这个时间长度100人和20人差不多。

点评

经验证,你所说的都是正确的。你是怎么得到这些结果的?  发表于 5 天前
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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的时候才能跑出来。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|Archiver|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2018-4-22 16:36 , Processed in 0.091761 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表