每日一题[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) 的个数为 \dbinom{n-m+1}m. 接下来我们求 x_m=\dbinom{n-m+1}m 的最大值,考虑\begin{split}\dfrac{x_{m+1}}{x_m}-1&=\dfrac{\dbinom{n-m}{m+1}}{\dbinom{n-m+1}{m}}-1\\ &=\dfrac{(n-m)!(n-2m+1)!m!}{(n-m+1)!(n-2m-1)!(m+1)!}-1\\ &=\dfrac{(n-2m+1)(n-2m)}{(n-m+1)(m+1)}-1\\ &=\dfrac{5m^2-(5n+2)m+n^2-1}{-m^2+nm+n+1},\end{split}考虑分子的零点,因此当m=\left[\dfrac{5n+2-\sqrt{5n^2+20n+24}}{10}\right]+1时,M_{(n,m)} 的个数最多.

3、根据第 (2) 小题的结果,当 n=2m 时,有x_m=\dbinom{m+1}{m}=m+1,此时序列 a_1,a_2,\cdots,a_m1,2,\cdots,m+1 的一个子排列,转化后的序列包含 22m-1 的都只有 1 个.考虑集合\begin{split} &\{1,3,5,\cdots,2m-1\},\\ &\{1,3,5,\cdots,2m\},\\ &\{1,4,6,\cdots,2m\},\\ &\{2,4,6,\cdots,2m\},\end{split}可得除 22m-1 以外的每个数都至少出现 2 次,因此 a 的值为 2,2m-1,出现的次数为 1

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

发表回复