若对任意的正整数 $m$，集合 $\{m,m+1,m+2,\cdots,m+99\}$ 的任意 $n(n \geqslant 3)$ 元子集中，总有 $3$ 个元素两两互素，求 $n$ 的最小值．
【难度】
【出处】
2015年全国高中数学联赛福建省预赛
【标注】
【答案】
$68$
【解析】
考察集合 $\{1,2,3,\cdots,100\}(m=1\text{ 时})$ 的 $67$ 元子集：
$P = \{2,4,6,\cdots,100,3,9,15,\cdots,99\}(\text{偶数与被}$ 3 $ \text{整除的奇数} )$．
显然 $P$ 中不存在 $3$ 个两两互素的元素．
所以，$n \leqslant 67$ 不符合要求．
引理： 对任意的正整数 $m$，集合 $\{m,m + 1,m +2,m +3,m+4,m+5\}$ 的任意 $5$ 元子集中，总有 $3$ 个元素两两元素互素．
引理的证明： 设集合 $A$ 是集合 $\{m,m + 1,m +2,m +3,m+4,m+5\}$ 的一个 $5$ 元子集．
由于 $m$、$ m+1$、$ m+2$、$ m+3$、$ m+4$、$ m+5$ 这 $6$ 个数中，$3$ 奇 $3$ 偶，恰有 $1$ 个 $5$ 的倍数，所以，若 $A$ 中含有 $3$ 个奇数，则这 $3$ 个奇数必两两互素，结论成立．
若 $A$ 中元素为 $2$ 奇 $3$ 偶．由于 $3$ 个偶数中至多有 $1$ 个为 $3$ 的倍数，至多有 $1$ 个为 $5$ 的倍数．因此，$3$ 个偶数中必有 $1$ 个数既不是 $3$ 的倍数，也不是 $5$ 的倍数，它与 $2$ 个奇数两两互素．结论成立．
所以，引理成立．
对任意的正整数 $m$，将集合 $\{m,m + 1,m +2,\cdots,m+99\}$ 划分成如下 $17$ 个集合：\[\begin{split}&A_{1} = \{m,m + 1,m +2,m +3,m+4,m+5\}, \\ &A_{2} = \{m+6,m + 7,m +8,m +9,m+10,m+11\},\\ &\cdots \cdots\\ &A_{16} = \{m+90,m + 91,m +92,m +93,m+94,m+95\}, \\ &A_{17} = \{m+96,m + 97,m +98,m +99\}, \end{split}\]显然上述 $17$ 个集合的两两交集为空集，并集为集合 $\{m,m + 1,m +2,\cdots,m+99\}$．
设集合 $M$ 是集合 $\{m,m + 1,m +2,\cdots,m+99\}$ 的 $68$ 元子集．
若集合 $M$ 有 $4$ 个元素来自集合 $A_{17}$．由于 $m$ 为奇数时，$m+96$、$m + 97$、$m +98$ 两两互素；当 $m$ 为偶数时，$m + 97$、$m +98$、$m+99$ 两两互素．因此，$M$ 中至少有 $3$ 个元素两两互素．
若集合 $M$ 至多 $3$ 个元素来自集合 $A_{17}$，则 $M$ 至少有 $65$ 个元素来自集合 $A_{1}$，$A_{2}$，$\cdots$，$A_{16}$．根据抽屉原理，$M$ 中至少有 $5$ 个元素来自同一个集合，不妨设它们来自集合 $A_{1}$，由前面的引理可知，它们中存在 $3$ 个两两互素的元素．
所以，集合 $M$ 中总有 $3$ 个两两互素的元素．
因此，$n = 68$ 符合要求，即对任意的正整数 $m$ 集合 $\{m,m + 1,m +2,\cdots,m+99\}$ 的任意 $68$ 元子集中，总有 $3$ 个元素的两两互素．
所以，$n$ 的最小值为 $68$．
$P = \{2,4,6,\cdots,100,3,9,15,\cdots,99\}(\text{偶数与被}$ 3 $ \text{整除的奇数} )$．
显然 $P$ 中不存在 $3$ 个两两互素的元素．
所以，$n \leqslant 67$ 不符合要求．
由于 $m$、$ m+1$、$ m+2$、$ m+3$、$ m+4$、$ m+5$ 这 $6$ 个数中，$3$ 奇 $3$ 偶，恰有 $1$ 个 $5$ 的倍数，所以，若 $A$ 中含有 $3$ 个奇数，则这 $3$ 个奇数必两两互素，结论成立．
若 $A$ 中元素为 $2$ 奇 $3$ 偶．由于 $3$ 个偶数中至多有 $1$ 个为 $3$ 的倍数，至多有 $1$ 个为 $5$ 的倍数．因此，$3$ 个偶数中必有 $1$ 个数既不是 $3$ 的倍数，也不是 $5$ 的倍数，它与 $2$ 个奇数两两互素．结论成立．
所以，引理成立．
对任意的正整数 $m$，将集合 $\{m,m + 1,m +2,\cdots,m+99\}$ 划分成如下 $17$ 个集合：\[\begin{split}&A_{1} = \{m,m + 1,m +2,m +3,m+4,m+5\}, \\ &A_{2} = \{m+6,m + 7,m +8,m +9,m+10,m+11\},\\ &\cdots \cdots\\ &A_{16} = \{m+90,m + 91,m +92,m +93,m+94,m+95\}, \\ &A_{17} = \{m+96,m + 97,m +98,m +99\}, \end{split}\]显然上述 $17$ 个集合的两两交集为空集，并集为集合 $\{m,m + 1,m +2,\cdots,m+99\}$．
设集合 $M$ 是集合 $\{m,m + 1,m +2,\cdots,m+99\}$ 的 $68$ 元子集．
若集合 $M$ 有 $4$ 个元素来自集合 $A_{17}$．由于 $m$ 为奇数时，$m+96$、$m + 97$、$m +98$ 两两互素；当 $m$ 为偶数时，$m + 97$、$m +98$、$m+99$ 两两互素．因此，$M$ 中至少有 $3$ 个元素两两互素．
若集合 $M$ 至多 $3$ 个元素来自集合 $A_{17}$，则 $M$ 至少有 $65$ 个元素来自集合 $A_{1}$，$A_{2}$，$\cdots$，$A_{16}$．根据抽屉原理，$M$ 中至少有 $5$ 个元素来自同一个集合，不妨设它们来自集合 $A_{1}$，由前面的引理可知，它们中存在 $3$ 个两两互素的元素．
所以，集合 $M$ 中总有 $3$ 个两两互素的元素．
因此，$n = 68$ 符合要求，即对任意的正整数 $m$ 集合 $\{m,m + 1,m +2,\cdots,m+99\}$ 的任意 $68$ 元子集中，总有 $3$ 个元素的两两互素．
所以，$n$ 的最小值为 $68$．
答案
解析
备注
