每日一题[2138]素数队列

设 $S=\{1,2,3,\cdots,2020\}$,如果 $S$ 中任意两个两两互质的数组成的集合中至少有一个质数,集合元素的个数 $n$ 的最小值为(       )

A.$15$

B.$16$

C.$17$

D.$18$

答案   B.

解析    首先,我们有 $n\geqslant 16$.事实上,取集合\[A_{0}=\left\{1,2^{2}, 3^{2}, 5^{2}, \cdots, 41^{2}, 43^{2}\right\},\]其元素,除 $1$ 以外,均为不超过 $43$ 的素数的平方,则 $A_{0} \subseteq S$,$\left|A_{0}\right|=15$,$ A_{0}$ 中任意两数互质,但其中无质数,这表明 $n\geqslant 16$. 其次,我们证明:对任意 $ A \subseteq S$,$ n=|A|=16$,$A$ 中任两数互质,则 $A$ 中必存在一个质数. 利用反证法,假设 $A$ 中无质数,记 $A=\left\{a_{1}, a_{2}, \cdots, a_{16}\right\}$,分两种情况讨论: [[case]]情形一[[/case]]若 $1 \notin A$,则 $a_{1}, a_{2}, \cdots, a_{16}$ 均为合数,又因为 $\left(a_{i}, a_{j}\right)=1$($1\leqslant i<j\leqslant 16$),所以 $a_{i}$ 与 $a_{j}$ 的质因数均不相同,设 $ a_{i}$ 的最小质因数为 $p_{i}$,不妨设 $p_{1}<p_{2}<\cdots<p_{16}$,则\[\begin{split}& a_{1} \geqslant p_{1}^{2} \geqslant 2^{2}, \\ &a_{2} \geqslant p_{2}^{2} \geqslant 3^{2}, \\ &\cdots, \\ &a_{15} \geqslant p_{15}^{2} \geqslant 47^{2}>2020,\end{split}\]矛盾. [[case]]情形二[[/case]]若 $1 \in A$,则不妨设 $a_{16}=1$,$ a_{1}, \cdots, a_{15}$ 均为合数,同情形一所设,同理有\[\begin{split} &a_{1} \geqslant p_{1}^{2} \geqslant 2^{2}, \\ &a_{2} \geqslant p_{2}^{2} \geqslant 3^{2}, \\ &\cdots, \\ &a_{15} \geqslant p_{15}^{2} \geqslant 47^{2}>2020,\end{split}\]矛盾. 综上所述,反设不成立,从而 $A$ 中必有质数,即 $n=|A|=16$ 时结论成立,因此所求的 $n$ 最小值为 $16$.

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

发表评论