MathLabs

第3题

令 S={1,2,3,…,280}S=\{1,2,3,\ldots,280\}。求最小整数n,使得S的每个n元子集都包含五个两两互质的数。
第 1/5 步:构造216元素障碍集合
A={m≤280:2∣m or 3∣m or 5∣m or 7∣m},∣A∣=216A=\{m\le280:2\mid m\text{ or }3\mid m\text{ or }5\mid m\text{ or }7\mid m\},\qquad |A|=216
详细分析

2、3、5的倍数由容斥原理有140+93+56−46−28−18+9=206个。7的倍数中尚未计入的恰为7、49、77、91、119、133、161、203、217、259这十个。因此A有216个元素。