每日一题[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$.

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

发表回复