1996第11届CMO试题

• 知识点

  >

  二试组合部分

略

设有 $a, b \in S$ 满足条件 $(a+b) | a b$．记 $c=(a,b)$，于是 $a=c a_{1}, b=c b_{1}$，其中 $a_{1}, b_{1} \in \mathbf{N}$ 且有 $\left(a_{1}, b_{1}\right)=1$，因而有 $c\left(a_{1}+b_{1}\right)=(a+b) | a b=c^{2} a_{1} b_{1}\left(a_{1}+b_{1}\right) | c a_{1} b_{1}$ 因为 $\left(a_{1}+b_{1}, a_{1}\right)=1,\left(a_{1}+b_{1}, b_{1}\right)=1$，故有 $\left(a_{1}+b_{1}\right) | c$ 因为 $a, b \in S$，所以 $a+b \leqslant 99$，即 $c\left(a_{1}+b_{1}\right) \leqslant 99$．故有 $3 \leqslant a_{1}+b_{1} \leqslant 9$．由此可知，$S$ 中满足条件 $(a+b) | a b$ 的不同数对共有 $23$ 对，如下
$a_{1}+b_{1}=3 :(6,3),(12,6),(18,9),(24,12),(30,15),(36,15),(36,18),(42,21),(48,24)$
$a_{1}+b_{1}=4 :(12,4),(24,8),(36,12),(48,16)$
$a_{1}+b_{1}=5 :(20,5),(40,10),(15,10),(30,20),(45,30)$
$a_{1}+b_{1}=6 :(30,6)$
$a_{1}+b_{1}=7 :(42,7),(35,14),(28,21)$
$a_{1}+b_{1}=8 :(40,24)$
$a_{1}+b_{1}=9 :(45,36)$
令 $M=\{6,12,15,18,20,21,24,35,40,42,45,48\}$，则 $|M|=12$ 且上述 $23$ 个数对中的每一对都至少包含 $M$ 中的 $1$ 个元素．因此，若令 $T = S -M$，则 $|T|= 38$ 且 $T$ 中任何两数都不满足题中 要求．可见，所求的最小自然数 $k\geqslant 39$．注意，下列 $12$ 个满足题中要求的数对互不相交：$(6,3),(12,4),(20,5),(42,7),(24,8),(18,9),(40,10),(35,14),(30,15),(48,16),(28,21),(45,36)$
对于 $S$ 的任一 $39$ 元子集 $R$，它只比 $S$ 少 $11$ 个元素，而这 $11$ 个
元素至多属于上述 $12$ 个数对中的 $11$ 对，从而必有 $12$ 对中的 $1$ 对属
于 $R$．
综上可知，所求的最小自然数 $k = 39$．