MathLabs

第3题

令 S={1,2,3,…,280}S=\{1,2,3,\ldots,280\}。求最小整数n,使得S的每个n元子集都包含五个两两互质的数。
第 5/5 步：迫使某一块含五个元素
上一步下一步
∣T∣=217 ⟹ ∣T∩(P∪A1∪A2∪A3∪B1∪B2)∣≥25>6⋅4|T|=217\ \Longrightarrow\ |T\cap(P\cup A_1\cup A_2\cup A_3\cup B_1\cup B_2)|\ge25>6\cdot4
详细分析

所选88个数的补集有192个元素。因此217元子集T与这88个数的并集至少相交25个。若六个块每个至多含T的四个元素,交集至多24个。故某块含有五个两两互质的数。结合前面的障碍,最小值为n=217。