每日一题[2830]稀疏集合

对正整数 $n$，记 ${I_n} = \left\{ {1,2, \cdots ,n} \right\}$，${P_n} = \left\{\dfrac{m}{\sqrt k }\mid m \in {I_n},k \in {I_n} \right\}$．

1、求集合 ${P_7}$ 中元素的个数．

2、若 ${P_n}$ 的子集 $A$ 中任意两个元素之和不是整数的平方，则称 $A$ 为"稀疏集"．求 $n$ 的最大值，使 ${P_n}$ 能分成两个不相交的稀疏集的并．

解析

1、本题考查对新定义的理解，关键在于考虑清楚可能重复的计算结果有几种情况．

当 $k = 4$ 时，$\left\{ {\dfrac{m}{\sqrt k }\mid m \in {I_7}} \right\}$ 中有 $3$ 个数与 ${I_7}$ 中的 $3$ 个数重复，因此 ${P_7}$ 中元素的个数为 $7 \times 7 - 3 = 46$．

2、本题考查推理与论证，通过试探得到可能的答案再进行论证是解决问题的关键．

注意到数字 $1,3,6,10,15$ 无法分成两个不相交的“稀疏集”，故可尝试证明答案为 $14$．

$n$ 不超过 $14$．    即证明：当 $n \geqslant 15$ 时，${P_n}$ 不能分成两个不相等的稀疏集的并．若不然，设 $A,B$ 为不相交的稀疏集，使 $A \cup B = {P_n} \supseteq {I_n}$．不妨设 $1 \in A$，则因为 $1 + 3 = {2^2}$，故 $3 \notin A$，即 $3 \in B$． 同理，$6 \in A,10 \in B$，又推得 $15 \in A$，但 $1 + 15 = {4^2}$，这与 $A$ 为稀疏集矛盾．

 $n$ 可以取 $14$．    即证明 ${P_{14}}$ 符合要求． 当 $k = 1$ 时，$\left\{ \dfrac{m}{\sqrt k }\mid m \in {I_{14}} \right\} = {I_{14}}$ 可分成两个稀疏集之并，事实上，只要取 $$\begin{split}{A_1} &= \left\{ {1,2,4,6,9,11,13} \right\} ,\\ {B_1} &= \left\{ {3,5,7,8,10,12,14} \right\},\end{split}$$ 则 ${A_1},{B_1}$ 为稀疏集，且 $${A_1} \cup {B_1} = {I_{14}}.$$ 当 $k = 4$ 时，集合 $\left\{\dfrac{m}{\sqrt k } \mid m \in {I_{14}}\right\}$ 中除整数外剩下的数组成集合 $$\left\{ {\dfrac{1}{2},\dfrac{3}{2},\dfrac{5}{2}, \cdots ,\dfrac{13}{2}} \right\},$$ 可求解为下面两稀疏集的并： $$\begin{split}{A_2} &= \left\{ {\dfrac{1}{2},\dfrac{5}{2},\dfrac{9}{2},\dfrac{11}{2}} \right\} ,\\ {B_2} &= \left\{ {\dfrac{3}{2},\dfrac{7}{2},\dfrac{13}{2}} \right\}.\end{split}$$ 当 $k = 9$ 时，集合 $\left\{ \dfrac{m}{\sqrt k }\mid m \in {I_{14}} \right\}$ 中除正整数外剩下的数组成集合 $$\left\{ {\dfrac{1}{3},\dfrac{2}{3},\dfrac{4}{3},\dfrac{5}{3}, \cdots ,\dfrac{13}{3},\dfrac{14}{3}} \right\},$$ 可分解为下面两稀疏集的并： $$\begin{split}{A_3} &= \left\{ {\dfrac{1}{3},\dfrac{4}{3},\dfrac{5}{3},\dfrac{10}{3},\dfrac{13}{3}} \right\} ,\\ {B_3} &= \left\{ {\dfrac{2}{3},\dfrac{7}{3},\dfrac{8}{3},\dfrac{11}{3},\dfrac{14}{3}} \right\}.\end{split}$$ 最后，集合 $C = \left\{\dfrac{m}{\sqrt k } \mid m \in {I_{14}},k \in {I_{14}},~\text{且}~k \ne 1,4,9 \right\}$ 中的数的分母均为无理数，它与 ${P_{14}}$ 中的任何其他数之和都不是整数，因此，令 $$\begin{split}A &= {A_1} \cup {A_2} \cup {A_3} \cup C ,\\ B &= {B_1} \cup {B_2} \cup {B_3},\end{split}$$ 则 $A$ 和 $B$ 是不相交的稀疏集，且 $A \cup B =P_{14}$． 综上可知，所求 $n$ 的最大值为 $14$．