查看数据源：5c872534210b28428f14d62c
设 $S=\{1,2,3,…,280\}$．求最小的正整数 $n$，使得 $S$ 的每个 有 $n$ 个 元素的子集都含有 $5$ 个两两互素的数．（中国）
【难度】
【出处】
1991年第32届IMO试题
【标注】
  • 知识点
    >
    二试数论部分
【答案】
略
【解析】
先估计 $n$ 的下界．
设 $A_i(i=2,3,5,7)$ 为 $S$ 中能被 $i$ 整除的正整数集合，$A=A_2\bigcup A_3\bigcup A_5\bigcup A_7$．
由容斥原理，可得
$\begin{aligned}
|A|&=|A_2|+|A_3|+|A_5|+|A_7|-|A_2\bigcup A_3|-|A_2\bigcap A_5|\\
&-|A_2\bigcap A_7|-|A_3\bigcap A_5|-|A_3\bigcap A_7|-|A_5\bigcap A_7|\\
&+|A_2\bigcap A_3\bigcap A_5|+|A_2\bigcap A_3\bigcap A_7|+|A_2\bigcap A_5\bigcap A_7|\\
&+|A_3\bigcap A_5\bigcap A_7|-|A_2\bigcap A_3\bigcap A_5\bigcap A_7|\\
&=\left[\dfrac{280}{2}\right]+\left[\dfrac{280}{3}\right]+\left[\dfrac{280}{5}\right]+\left[\dfrac{280}{7}\right]-\left[\dfrac{280}{2\times 3}\right]-\left[\dfrac{280}{2\times 5}\right]\\
&-\left[\dfrac{280}{2\times 7}\right]-\left[\dfrac{280}{3\times 5}\right]-\left[\dfrac{280}{3\times 7}\right]-\left[\dfrac{280}{5\times 7}\right]+\left[\dfrac{280}{2\times 3\times 5}\right]\\
&+\left[\dfrac{280}{2\times 3\times 7}\right]+\left[\dfrac{280}{2\times 5\times 7}\right]+\left[\dfrac{280}{3\times 5\times 7}\right]-\left[\dfrac{280}{2\times 3\times 5\times 7}\right]\\
&=140+93+5++40-46-28-20-18-13-8+9+6+4+2-1\\
&=216
\end{aligned}$
在 $S$ 中取集 $A$ 中的 $216$ 个元素，由抽屉原则，这 $216$ 个元素中任 $5$ 个必有两个属于 $A_2,A_3,A_5,A_7$ 中某一个集合，所以它们不互素，即从这 $216$ 个数中找不到 $5$ 个两两互素的数．所以 $n\geqslant 217$．
下面我们来证明 $S$ 中任意 $217$ 个元素中必有 $5$ 个数两两互素．令
$B_1=\{1和S中的一切素数\}$
$B_2=\{2^2,3^2,5^2,7^2,11^2,13^2\}$
$B_3=\{2\times 131,3\times 89,5\times 53,7\times 37,11\times 23,13\times 19\}$
$B_4=\{2\times 127,3\times 83,5\times 47,7\times 31,11\times 19,13\times 17\}$
$B_5=\{2\times 113,3\times 79,5\times 43,7\times 29,11\times 17\}$
$B_6=\{2\times 109,3\times 73,5\times 41,7\times 23,11\times 13\}$
$B=B_1\bigcup B_2\bigcup B_3\bigcup B_4\bigcup B_5\bigcup B_6$
易知 $B_i(i=1,2,\cdots,6)$ 中的数两两互素，且 $B_i\bigcap B_j=\varnothing(i\leqslant i<j\leqslant 6)$．
$|B_1|=60,|B_2|=|B_3|=|B_4|=6,|B_5|=|B_6|=5$，所以
$|B|=60+6\times 3+5\times 2=88$
$|S\setminus B|=280-88=192$
$S$ 中的任意 $217$ 个元素中至少有 $217-192=25$ 个元素属于 $B$．由抽屉原则，这 $25$ 个元素中至少有 $\left[\dfrac{25}{6}\right]+1=5$ 个元素属于某个 $B_i(1\leqslant i\leqslant 6)$，这 $5$ 个元素两两互素．
综上可得，所求的 $n$ 的最小值为 $217$．
答案 解析 备注
0.164340s