设 $M=(1,2,\cdots,2008)$ 是前 $2008$ 个正整数组成的集合，$A=\{a_1,a_2,\cdots,a_{30}\}$ 是 $M$ 的一个 $30$ 元子集，已知 $A$ 中的元素两两互质，证明 $A$ 中至少有一半元素是质数．
【难度】
【出处】
2008年全国高中数学联赛山西省预赛
【标注】
【答案】
略
【解析】
先证明：$A$ 中 $16$ 个元素中必有一个是质数．
为此，任取 $16$ 个元素，不妨设为 $a_1,a_2,\cdots,a_{16}$ 若其中没有质数，则它们中至多一个为 $1$，其余 $15$ 个皆为合数，设 $a_1,a_2,\cdots,a_{15}$ 都是合数，则每个数皆可分解成至少两个质因数的乘积．若 $p_i$ 是 $a_i$ 的最小质因数，则 $p_i\leqslant \sqrt {a_i}(i=1,2,\cdots,15)$．由于 $A$ 中的数两两互质，则 $p_1,p_2,\cdots,p_{15}$ 互不相同，而将全体质数自小到大排列，第 $15$ 个质数是 $47$，所以，若 $p_1$ 是 $p_1,p_2,\cdots,p_{15}$ 中的最大数，即有 $p_1\geqslant 47$，于是 $a_1\geqslant {p_1}^2\geqslant {47}^2>2008$，即 $a_1\notin M$，矛盾！
因此 $a_1,a_2,\cdots,a_{15}$ 中必有质数，不妨设 $a_1$ 为质数．今从集合 $A$ 中去掉 $a_1$，在剩下的 $29$ 个元素中，再次进行同样的讨论，可知其中的 $16$ 个元素中也必有一个是质数，设为 $a_2$．如此下去，可以连续进行 $15$ 次，每次都可从 $A$ 中取到一个新的质数，因此 $A$ 中至少有 $15$ 个质数．
为此，任取 $16$ 个元素，不妨设为 $a_1,a_2,\cdots,a_{16}$ 若其中没有质数，则它们中至多一个为 $1$，其余 $15$ 个皆为合数，设 $a_1,a_2,\cdots,a_{15}$ 都是合数，则每个数皆可分解成至少两个质因数的乘积．若 $p_i$ 是 $a_i$ 的最小质因数，则 $p_i\leqslant \sqrt {a_i}(i=1,2,\cdots,15)$．由于 $A$ 中的数两两互质，则 $p_1,p_2,\cdots,p_{15}$ 互不相同，而将全体质数自小到大排列，第 $15$ 个质数是 $47$，所以，若 $p_1$ 是 $p_1,p_2,\cdots,p_{15}$ 中的最大数，即有 $p_1\geqslant 47$，于是 $a_1\geqslant {p_1}^2\geqslant {47}^2>2008$，即 $a_1\notin M$，矛盾！
因此 $a_1,a_2,\cdots,a_{15}$ 中必有质数，不妨设 $a_1$ 为质数．今从集合 $A$ 中去掉 $a_1$，在剩下的 $29$ 个元素中，再次进行同样的讨论，可知其中的 $16$ 个元素中也必有一个是质数，设为 $a_2$．如此下去，可以连续进行 $15$ 次，每次都可从 $A$ 中取到一个新的质数，因此 $A$ 中至少有 $15$ 个质数．
答案
解析
备注
