MathLabs

第3题

令 S={1,2,3,…,280}S=\{1,2,3,\ldots,280\}。求最小整数n,使得S的每个n元子集都包含五个两两互质的数。
第 2/5 步：用四个素因子排除五个数
上一步下一步
∣A∣=216 ⟹ A has no five pairwise coprime elements|A|=216\ \Longrightarrow\ A\text{ has no five pairwise coprime elements}
详细分析

A中每个数至少被2、3、5、7之一整除。若五个数两两互质,这四个素数必须分配给五个不同的数,违背抽屉原理。因此n至少为217。