一个组合问题
某委员会召开了40次会议，每次10人出席，委员会任何两个成员都只同时出席一次会议，该委员会最少有多少人？ 这个题目相当于找到n,使得A(n,18,10)>=40 (任何两个10个比特为1的n比特数，两两之间不同的比特不小于18）可惜表格https://oeis.org/wiki/Index_to_OEIS:_Section_Aa#Andw 中没有A(n,18,10) http://www.win.tue.nl/~aeb/codes/Andw.html#d18
中给出A(82,18,10) = 41，也就是82个成员够了 厉害啊，构造出82个成员很难 本帖最后由 王守恩 于 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-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: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}。 证明小于82个成员不能满足条件相对容易点，构造82个成员满足条件比较困难 链接里面其它数据基本上都给出了构造结果，但是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个差。
页:
[1]
2