[组合] 从1-2000中最多能选出多少个数使得任意两数之差不为

hbghlyj

(1)从1-2000中最多能选出多少个数使得选出的数中任意两数之差不为5,7,11,17,29
构造一个立方体
同行相邻的差为8，同列相邻的差为13，全部加19又叠在上面
若两个数的差不为5,7,11,17,29这两个数就连一条边，限制越多，连的边越少，反而越简单
(2)从1-2000中最多能选出多少个数使得选出的数中任意两数之差不为5,8,11,12,19
似乎是用ford-fulkerson算法

(1)用mma穷举，鉴于阶乘爆炸，我们只有五个样本20,21,22,23,24，均已验证元素个数最大
In[2]:= Select[Subsets[Range[24],{12}],Intersection[#,Join[#+8,#+13,#+19]]=={}&]
Out[2]= {{1,2,3,6,7,8,12,13,17,18,23,24},{1,2,3,7,8,12,13,17,18,19,23,24},{1,2,6,7,8,11,12,13,17,18,22,23},{1,2,6,7,8,12,13,17,18,22,23,24},{1,2,6,7,11,12,13,16,17,18,22,23},{1,2,7,8,12,13,17,18,19,22,23,24},{2,3,7,8,9,12,13,14,18,19,23,24},{2,3,7,8,12,13,14,17,18,19,23,24}}

In[3]:= Select[Subsets[Range[23],{12}],Intersection[#,Join[#+8,#+13,#+19]]=={}&]
Out[3]= {{1,2,6,7,8,11,12,13,17,18,22,23},{1,2,6,7,11,12,13,16,17,18,22,23}}

In[4]:= Select[Subsets[Range[21],{10}],Intersection[#,Join[#+8,#+13,#+19]]=={}&]
Out[4]= {{1,2,3,6,7,8,12,13,17,18},{1,2,3,7,8,12,13,17,18,19},{1,2,6,7,8,11,12,13,17,18},{1,2,6,7,11,12,13,16,17,18},{1,5,6,7,10,11,12,16,17,21},{1,5,6,10,11,12,15,16,17,21},{2,3,4,7,8,9,13,14,18,19},{2,3,4,8,9,13,14,18,19,20},{2,3,7,8,9,12,13,14,18,19},{2,3,7,8,12,13,14,17,18,19},{3,4,5,8,9,10,14,15,19,20},{3,4,5,9,10,14,15,19,20,21},{3,4,8,9,10,13,14,15,19,20},{3,4,8,9,13,14,15,18,19,20},{4,5,6,9,10,11,15,16,20,21},{4,5,9,10,11,14,15,16,20,21},{4,5,9,10,14,15,16,19,20,21}}

In[5]:= Select[Subsets[Range[22],{11}],Intersection[#,Join[#+8,#+13,#+19]]=={}&]
Out[5]= {{1,2,6,7,8,11,12,13,17,18,22},{1,2,6,7,11,12,13,16,17,18,22},{1,5,6,7,10,11,12,16,17,21,22},{1,5,6,10,11,12,15,16,17,21,22}}

In[7]:= Select[Subsets[Range[20],{10}],Intersection[#,Join[#+8,#+13,#+19]]=={}&]
Out[7]= {{1,2,3,6,7,8,12,13,17,18},{1,2,3,7,8,12,13,17,18,19},{1,2,6,7,8,11,12,13,17,18},{1,2,6,7,11,12,13,16,17,18},{2,3,4,7,8,9,13,14,18,19},{2,3,4,8,9,13,14,18,19,20},{2,3,7,8,9,12,13,14,18,19},{2,3,7,8,12,13,14,17,18,19},{3,4,5,8,9,10,14,15,19,20},{3,4,8,9,10,13,14,15,19,20},{3,4,8,9,13,14,15,18,19,20}}

In[8]:= Select[Subsets[Range[19],{10}],Intersection[#,Join[#+8,#+13,#+19]]=={}&]
Out[8]= {{1,2,3,6,7,8,12,13,17,18},{1,2,3,7,8,12,13,17,18,19},{1,2,6,7,8,11,12,13,17,18},{1,2,6,7,11,12,13,16,17,18},{2,3,4,7,8,9,13,14,18,19},{2,3,7,8,9,12,13,14,18,19},{2,3,7,8,12,13,14,17,18,19}}
最后一个数据不算，因为它相当于把Intersection[#,#+19]=={}&这个条件弃了

引语中指的是什么神奇的方法？请不吝赐教

hbghlyj

下面是从互联网上收集的类似题
(1)在1～200这200个自然数中，选出一些数，要求其中任意两数之差都不等于1,3,4，那么最多能选出多少个数．
因为其中任意两数之差都不等于1,3,4，那么相邻两个数差只能是2,5，不能连续是2，不然会出现4，因此差最佳应选2,5,2,5,2,5…，选的数是1,3,8,10,15,17,22…；相当于每7个数选2个（1到7选2个，8到14选2个），200÷7=28…4，最后4个正好可以选2个，因此总数=28×2+2=58
(2)从1到20的正整数中,至少任选几个数,就可以保证其中一定包括两个数,它们的差是12
法①将1到20的正整数放入{20,8},{19,7},{18,6},{17,5},{16,4},{15,3},{14,2},{13,1},{9},{10},{11},{12}这12 个抽屉中.只要有两个数取自同一个抽屉,那么它们的差就等于 12,,根据抽屉原理至少任选13个数.
法②可把这20个数分为三部分：1到8,9到12,13到20。要包含两个数的差是12，只有在1到8和13到20里选出。
因为是任意选，所以，首先要包含9到12这四个数，然后要包含1到8这八个数，再从13到20里任选一个数。
也就是从这20个数中要任选出13个数来，就必有两个数的差是12。
(3)1到2000内最多能选出多少个数,使任意两数之差不为4或7
(4)在1到2000这2000个数中,至多能取几个数使其中任意两个数的和是26的倍数
$26=1+25=2+23=\cdots=12+14=13+13$如果选了剩余类1,2,...,12,14,...,25中的数，则至多能取两个数。如果选了剩余类13中的数，则至多能取$\lfloor\frac{2000+13}{26}\rfloor=77$个数。如果选了剩余类0中的数，则至多能取$\lfloor\frac{2000}{26}\rfloor=76$个数。所以至多能取77个数。
(5)从正整数1到1000中，最多可取出多少个数，使得所取出的数中任意三个数之和能被18整除。
能选出55个数
第一个数为18  18/18=1
第二个数为36  36/18=2
   :
   :
第五十五个数为990   990/18=55
(6)1到100中最多可以选出多少个数，使得这些数中任意两个数的差都不整除它们的和？
自然数按被3除得的余数可以分成3类，即余数是：0、1、2，被3除余1的所有数，任两个数相加的和被3除余2，差能被3整除，符合要求，对被3除余2的所有数也如此，即2+2=4，4÷3还是余1，在1到1000中，被3除余1的有334个，余0、2的333个．因此取被3除余1的334个，这些数符合题意；故答案为：334．
(7)在1~2001这2001个数中最多可取出多少个数，使得这些数中任意三个数的和都不能被7整除？
在1~2001这2001个数中，要三个数的和不能被7整除，必须且只需这三个数被7除的余数之和不能被7整除，因此，以7为模，把这2001个数分成7类。因2001=7*285+6，故7的倍数有285个，其余6类各有286个数。
因0≡0+0+0≡0+1+6≡0+2+5≡0+3+4≡1+1+5≡1+2+4≡1+3+3≡2+2+3≡6+6+2≡6+5+3≡6+4+4≡5+5+4，故要取出的数中，任意三个数的和都不能被7整除，7的倍数至多只能有2个，余数为1、2的两类可以都取，共2+2×286=574个数。
如果取出的数多于574个，那么,不管是否取2个7的倍数，都要其他6类中的3类数，$C_6^3$=20,对照上述同余式，可以一一排除其可能性。例如余数为1、2、3的三类，1+3+3=2+2+3≡0，有一个余数为3的数就不能有2个余数为2的数；有2个余数为3的数就不能有余数为1的数。
满足题设的余数为1、2、3的数最多为288个，矛盾。余者类推。 综上，在1~2001这2001个数中最多可取出574个数，使得这些数中任意三个数的和都不能被7整除。