已知集合 Sn={1,2,3,⋯,n},A⊆Sn,当 x∈A 时,x−1∉A 且 x+1∉A,则称 x 为集合 A 中的孤立元素.设集合 M(n,m) 为集合 Sn 的一个 m 元子集,且 M(n,m) 中的元素均为孤立元素.
1、写出所有符合条件的集合 M(4,2).
2、当 m 取何值时,所有可能的集合 M(n,m) 的个数最多?说明理由.
3、设 a∈S2m 且 a 在所有可能的集合 M(2m,m) 中出现的次数最少,求出 a 的值及其出现的次数,并说明理由.
解析
1、根据题意,M(4,2) 的所有可能为{1,3},{1,4},{2,4}.
2、M(n,m) 中的元素均为孤立元素即 M(n,m) 中的任意两个元素之差不小于 2,因此可以从 {1,2,⋯,n−m+1} 中选出 m 个,从小排列为a1,a2,⋯,am,然后将其转化为a1,a2+1,a3+2,⋯,am+m−1,这样任意两个数的差都不小于 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_m 是 1,2,\cdots,m+1 的一个子排列,转化后的序列包含 2 和 2m-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}可得除 2 和 2m-1 以外的每个数都至少出现 2 次,因此 a 的值为 2,2m-1,出现的次数为 1.