一个组合问题

Sirius

某委员会召开了40次会议，每次10人出席，委员会任何两个成员都只同时出席一次会议，该委员会最少有多少人？

mathe

这个题目相当于找到n,使得A(n,18,10)>=40 (任何两个10个比特为1的n比特数，两两之间不同的比特不小于18）
可惜表格https://oeis.org/wiki/Index_to_OEIS:_Section_Aa#Andw 中没有A(n,18,10)

mathe

http://www.win.tue.nl/~aeb/codes/Andw.html#d18
中给出A(82,18,10) = 41，也就是82个成员够了

Sirius

厉害啊，构造出82个成员很难

王守恩

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):
表格内数字有不对的，但节点数字无误。

wayne

我联想到了小时候看的一本书，讲的 寇克曼女生问题 和史坦纳三元集，陆家羲 的故事，是啥书，竟然忘了

王守恩

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)}\)

王守恩

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}。

Sirius

证明小于82个成员不能满足条件相对容易点，构造82个成员满足条件比较困难

mathe

链接里面其它数据基本上都给出了构造结果，但是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个差。