$\{1,2,\cdots,n\}$的任意一个$k$元子集中都存在$3$个元素两两互素，求$k$的最小值

abababa

集合$A_n=\{1,2,\cdots,n\}$的任意一个$k$元子集中都存在$3$个元素两两互素，求$k$的最小值。

答案是$[\frac{n}{2}]+[\frac{n}{3}]-[\frac{n}{6}]+1$，其中$[x]$表示不超过$x$的最大整数。

按这个答案来看，应该是设出一个集合$T_n=\{x\in A_n:2\mid x或3\mid x\}$，然后$|T_n|$就等于$[\frac{n}{2}]+[\frac{n}{3}]-[\frac{n}{6}]$。根据抽屉原理，$T_n$中的任意三个元素中都至少存在两个，这两个或者都能被$2$整除，或者都能被$3$整除，就不能两两互素了，所以$k\ge|T_n|+1$，然后按答案，应该是证明$k=|T_n|+1$。之后要怎么证明呢？

abababa

好像有点思路了，下面用$\lor$表示或。然后先算前6个，再归纳。

当$4\le n\le9$时，直接验证可知$A_n$中合数有$\abs{T_n}-2$个，所以对$A_n$的任意一个$\abs{T_n}+1$元子集，里面至多有$\abs{T_n}-2$个合数，其它的都是素数或者是1，能从中选出$3$个，这$3$个元素两两互素，命题成立。

假设当$n=m$时命题成立，则当$n=m+6$时，设$B$是$A_{m+6}$的任意一个$\abs{T_{m+6}}+1$元子集。
1.当$\abs{B\cap A_m}\ge\abs{T_m}+1$时，可以选择$\abs{T_m}+1$个$B\cap A_m$中的元素，由于选出的元素都属于$A_m$，由归纳假设知其中存在$3$个元素两两互素，显然这$3$个元素也都属于$B$，于是$B$中存在$3$个元素两两互素，命题成立。
2.当$\abs{B\cap A_m}\le\abs{T_m}$时，因为连续$6$个整数中有$4$个能被$2$或$3$整除，所以
\begin{align*}
\abs{T_{m+6}}
&=\abs{\{x\in A_{m+6}: 2\mid x\lor3\mid x\}}\\
&= \abs{\{x\in A_{m}: 2\mid x\lor3\mid x\}}+\abs{\{x\in\{m+1,m+2,m+3,m+4,m+5,m+6\}: 2\mid x\lor3\mid x\}}\\
&=\abs{T_{m}}+4
\end{align*}

于是
\[\abs{B}=\abs{T_{m+6}}+1=\abs{T_m}+4+1=\abs{T_m}+5\]

但$\abs{B\cap A_m}\le\abs{T_m}$，结合上式可知$\abs{B\setminus A_m}\ge5$(1)，而$(B\setminus A_m)$中的元素全属于$A_{m+6}$但不属于$A_m$，所以$(B\setminus A_m)\subseteq\{m+1,m+2,m+3,m+4,m+5,m+6\}$(2)，由(1)(2)可知$B$中必定包含$m+1,m+2,m+3,m+4,m+5,m+6$中的$5$个数，而从连续$6$个数中任意取出$5$个，都存在$3$个数两两互素，因此命题成立。