数学研发论坛

 找回密码
 欢迎注册
查看: 371|回复: 14

[讨论] 一个组合问题

[复制链接]
发表于 2018-4-22 11:25:02 | 显示全部楼层 |阅读模式

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

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

x
某委员会召开了40次会议,每次10人出席,委员会任何两个成员都只同时出席一次会议,该委员会最少有多少人?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-4-22 18:54:14 | 显示全部楼层
这个题目相当于找到n,使得A(n,18,10)>=40 (任何两个10个比特为1的n比特数,两两之间不同的比特不小于18)
可惜表格https://oeis.org/wiki/Index_to_OEIS:_Section_Aa#Andw 中没有A(n,18,10)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-4-22 18:59:04 | 显示全部楼层
http://www.win.tue.nl/~aeb/codes/Andw.html#d18
中给出A(82,18,10) = 41,也就是82个成员够了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-4-22 21:04:43 | 显示全部楼层
厉害啊,构造出82个成员很难
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-4-23 14:57:01 | 显示全部楼层
本帖最后由 王守恩 于 2018-4-23 20:25 编辑
mathe 发表于 2018-4-22 18:59
http://www.win.tue.nl/~aeb/codes/Andw.html#d18
中给出A(82,18,10) = 41,也就是82个成员够了


                                总人数,每次人数,开会次数计算
                 每次3人  每次4人  每次5人  每次6人  每次7人  每次8人  每次9人  每次10人
总数5人          2             1            1         
总数6人          4             1            1            1         
总数7人          7             2            1            1             1      
总数8人          8             2            1            1             1           1
总数9人        12             3            1            1             1           1            1
总数10人      13             5            2            1             1           1            1             1   
总数11人      17             6            2            1             1           1            1             1
总数12人      20             9            3            2             1           1            1             1
总数13人      26           13            3            2             1           1            1             1
总数14人      28           14            4            2             2           1            1             1
总数15人      35           15            6            3             2           1            1             1
总数16人      37           20            6            3             2           2            1             1      
总数17人      44           20            7            3             2           2            1             1
总数18人      48           22            9            4             3           2            2             1   
总数19人      57           25          12            4             3           2            2             1   
总数20人      60           30          16            5             3           2            2             2
总数21人      70           31          21            7             3           3            2             2
总数22人      73           37          21            7             4           3            2             2
总数23人      83           40          23            8             4           3            2             2
总数24人      88           42          24            9             4           3            3             2  
总数25人    100           50          30          10             5           3            3             2  
总数26人    104           52          30          13             5           4            3             2
总数27人    117           54          31          14             6           4            3             3   
总数28人    121           63          33          16             8           4            3             3   
总数29人    134           65          34          20             8           4            3             3   
总数30人    140           67          36          25             9           5            4             3   
总数31人    155           76          38          31             9           5            4             3
总数32人    160           80          41          31           10           5            4             3  
再给出一些节点上的数据(限于篇幅,不一 一列出)
     每次3人,总人数/开会次数
3/1,7/7,9/12,13/26,15/35,19/57,21/70,25/100,27/117,31/155
33/176,37/222,39/247,43/301,45/330,49/392,51/425,55/495,57/532,61/610
     每次4人,总人数/开会次数
4/1,13/13,16/20,25/50,28/63,37/111,40/130,49/196,52/221,61/305,
64/336,73/438,76/475,85/595,88/638,97/776,100/825,109/981,112/1036,121/1210
     每次5人,总人数/开会次数
5/1,21/21,25/30,41/82,45/99,61/183,65/208,81/324,/85/357,101/505
105/546,121/726,125/775,141/987,145/1044,161/1288,165/1353,181/1629,185/1702,201/2010
     每次6人,总人数/开会次数
6/1,31/31,36/42,61/122,66/143,91/273,96/304,121/484,126/525,151/755
156/806,181/1086,186/1147,211/1477,216/1548,241/1928,246/2009,271/2439,276/2530,301/3010
     每次7人,总人数/开会次数
7/1,43/43,49/56,85/170,91/195,127/381,133/418,169/676,175/725,211/1055
217/1116,253/1518,259/1591,295/2065,301/2150,337/2696,343/2793,379/3411,385/3520,421/4210
     每次8人,总人数/开会次数
8/1,57/57,64/72,113/226,120/255,169/507,176/550,225/900,232/957,281/1405
288/1476,337/2022,344/2107,393/2751,400/2850,449/3592,456/3705,505/4545,512/4672,561/5610
     每次9人,总人数/开会次数
9/1,73/73,81/90,145/290,153/323,217/651,225/700,289/1156,297/1221,361/1805
369/1886,433/2598,441/3695,505/3535,513/3648,577/4616,585/4745,649/5841,657/5986,721/7210
     每次10人,总人数/开会次数
10/1,91/91,100/110,181/362,190/399,271/813,280/868,361/1444,370/1517,451/2255
460/2346,541/3246,550/3355,631/4417,640/4544,721/5768,730/5913,811/7299,820/7462,901/9010
..........
有兴趣的网友,不妨验算一下?



补充内容 (2018-4-25 05:53):
表格内数字有不对的,但节点数字无误。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-4-23 22:02:24 | 显示全部楼层
我联想到了小时候看的一本书,讲的 寇克曼女生问题 和史坦纳三元集,陆家羲 的故事,是啥书,竟然忘了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-4-24 09:21:19 | 显示全部楼层
本帖最后由 王守恩 于 2018-4-24 15:18 编辑
wayne 发表于 2018-4-23 22:02
我联想到了小时候看的一本书,讲的 寇克曼女生问题 和史坦纳三元集,陆家羲 的故事,是啥书,竟然忘了


补充一下:
所谓节点,是指最多的开会次数(控制点),

\(\D最多的开会次数=\frac{A×(A-1)}{B×(B-1)}=整数\)

\(\ A=总人数,B=每次开会人数,在2种情况下都是可以的:\)

\(第1种情况,A 是 B 倍数的同时,(A - 1) 是 (B - 1) 的倍数,\)

\(第2种情况,(A - 1) 是 B×(B - 1) 的倍数。\)

对于一般的开会次数估算:

\(\D一般的开会次数估算<\frac{A×(A-1)}{B×(B-1)}\)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-4-25 10:16:26 | 显示全部楼层
本帖最后由 王守恩 于 2018-4-25 10:20 编辑
wayne 发表于 2018-4-23 22:02
我联想到了小时候看的一本书,讲的 寇克曼女生问题 和史坦纳三元集,陆家羲 的故事,是啥书,竟然忘了


1850年,科克曼在《女士与先生之日记》杂志上发表了题为的文章,提出了15个女学生问题:一位女教师每天带领好班上的15名女生去散步,她把这些女生按3人一组分成5组,问能不能作出一个连续散步7天的计划,使得任意两个女生曾被分到一组且仅被分到一组,也就是说,随便从15人中挑出 2人,她俩在一周所分成的35个小组里必在一组中见过一面,且仅见一面.
科克曼在同一刊物上公布了他自己给出的一个答案如下(1至15代表15个女生):

星期日 {1, 2, 3},{4, 8, 12},{5, 10, 15},{6, 11, 13},{7, 9, 14};

星期一 {1, 4, 5},{2, 8, 10},{3, 13, 14},{6, 9, 15},{7, 11, 12};

星期二 {1, 6, 7},{2, 9, 11},{3, 12, 15},{4, 10, 14},{5, 8, 13};

星期三 {1, 8, 9},{2,12,14},{3, 5, 6}, {4, 11, 15},{7, 10, 13};

星期四 {1, 10, 11},{2, 13, 15},{3, 4, 7},{5, 9, 12},{6, 8, 14};

星期五 {1, 12, 13},{2, 4, 6},{3, 9, 10},{5, 11, 14},{7, 8, 15};

星期六 {1, 14, 15},{2, 5, 7},{3, 8 ,11},{4, 9, 13},{6, 10, 12}。

点评

此题等同: 每次3人节点中的一个,总人数/开会次数=15/35。  发表于 2018-4-25 10:29
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-4-25 23:27:38 | 显示全部楼层
证明小于82个成员不能满足条件相对容易点,构造82个成员满足条件比较困难
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-4-26 11:10:16 | 显示全部楼层
链接里面其它数据基本上都给出了构造结果,但是A(82,18,10)=41没有给出方案。
但是根据其它类似数据,我们可以猜测它是
从0,1,2,...,40(mod 41)中挑出10个数,将它们再分成两组。组内两两求差(模41),要求得到的所有差互不相同。
需要注意,比如0和1在一组,那么它们会同时形成差1-0=1和0-1=40.
由于不同的数之差不能出现0,那么最多40个差。而每组5个数时,正好每组20个差,共40个差。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2018-5-26 04:06 , Processed in 0.078235 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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