math-ai/BlueMO

1{2    "source_file": "./raw_volume-zh/volume1/exercise5.tex",3    "problem_type": "calculation",4    "problem": "问题12 设 $S=\\{1,2, \\cdots, 50\\}$. 求最小自然数 $k$, 使 $S$ 的任一 $k$ 元子集中都存在两个不同的数 $a$ 和 $b$, 满足 $(a+b) \\mid a b$.",5    "solution": "设有 $a 、 b \\in S$ 满足 $(a+b) \\mid 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, a_1 \\neq b_1$, 不妨设 $a_1>b_1$. 由于 $a+b= c\\left(a_1+b_1\\right), a b=c^2 a_1 b_1$, 因此 $\\left(a_1+b_1\\right) \\mid 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) \\mid c$. 而 $a+b \\leqslant 99$, 即 $c\\left(a_1+b_1\\right) \\leqslant 99$, 所以 $3 \\leqslant a_1+b_1 \\leqslant 9$. 由此可知, $S$ 中满足 $(a+b) \\mid a b$ 的不同数对 $(a, b)$ 共有 23 对: $a_1+b_1=3$ 时, 有 $(6,3) ，(12,6) ，(18,9) ，(24,12) ，(30,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)$.\n令 $M=\\{6,12,15,18,20,21,24,35,40,42,45,48\\}$. 则上述 23 个数对中的每一个数对都至少包含 $M$ 中的 1 个元素.\n令 $T=S-M$. 则 $T$ 中任何两数都不能成为满足要求的数对 $(a, b)$. 因为 $|T|=38$, 所以所求最小自然数 $K \\geqslant 39$.\n另一方面,下列 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$.",6    "remark": "",7    "figures": []8}