每日一题[2110]构建对应

已知集合 Sn={1,2,3,,n}ASn,当 xA 时,x1Ax+1A,则称 x 为集合 A 中的孤立元素.设集合 M(n,m) 为集合 Sn 的一个 m 元子集,且 M(n,m) 中的元素均为孤立元素.

1、写出所有符合条件的集合 M(4,2)

2、当 m 取何值时,所有可能的集合 M(n,m) 的个数最多?说明理由.

3、设 aS2ma 在所有可能的集合 M(2m,m) 中出现的次数最少,求出 a 的值及其出现的次数,并说明理由.

解析

1、根据题意,M(4,2) 的所有可能为{1,3},{1,4},{2,4}.

2、M(n,m) 中的元素均为孤立元素即 M(n,m) 中的任意两个元素之差不小于 2,因此可以从 {1,2,,nm+1} 中选出 m 个,从小排列为a1,a2,,am,然后将其转化为a1,a2+1,a3+2,,am+m1,这样任意两个数的差都不小于 2,且这个过程是一一对应的(例如 M(4,2) 中的 3 个集合分别由 1,2;1,3;2,3 得到).这样就有 M(n,m) 的个数为 (nm+1m). 接下来我们求 xm=(nm+1m) 的最大值,考虑xm+1xm1=(nmm+1)(nm+1m)1=(nm)!(n2m+1)!m!(nm+1)!(n2m1)!(m+1)!1=(n2m+1)(n2m)(nm+1)(m+1)1=5m2(5n+2)m+n21m2+nm+n+1,考虑分子的零点,因此当m=[5n+25n2+20n+2410]+1时,M(n,m) 的个数最多.

3、根据第 (2) 小题的结果,当 n=2m 时,有xm=(m+1m)=m+1,此时序列 a1,a2,,am1,2,,m+1 的一个子排列,转化后的序列包含 22m1 的都只有 1 个.考虑集合{1,3,5,,2m1},{1,3,5,,2m},{1,4,6,,2m},{2,4,6,,2m},可得除 22m1 以外的每个数都至少出现 2 次,因此 a 的值为 2,2m1,出现的次数为 1

此条目发表在每日一题分类目录,贴了标签。将固定链接加入收藏夹。

发表回复