每日一题[2110]构建对应

已知集合 $S_n=\{1,2,3,\cdots,n\}$，$A\subseteq S_n$，当 $x\in A$ 时，$x-1\notin A$ 且 $x+1\notin A$，则称 $x$ 为集合 $A$ 中的孤立元素．设集合 $M_{(n,m)}$ 为集合 $S_n$ 的一个 $m$ 元子集，且 $M_{(n,m)}$ 中的元素均为孤立元素．

1、写出所有符合条件的集合 $M_{(4,2)}$．

2、当 $m$ 取何值时，所有可能的集合 $M_{(n,m)}$ 的个数最多？说明理由．

3、设 $a\in S_{2m}$ 且 $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,\cdots,n-m+1\}$ 中选出 $m$ 个，从小排列为 $$a_1,a_2,\cdots,a_m,$$ 然后将其转化为 $$a_1,a_2+1,a_3+2,\cdots,a_m+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$．