MathLabs

Problem 3

Let S={1,2,3,…,280}S=\{1,2,3,\ldots,280\}. Find the smallest integer n such that each n-element subset of S contains five numbers which are pairwise relatively prime.
Step 1 of 5: Build a 216-element obstruction
Previous stepNext step
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
Detailed analysis

The multiples of 2,3,5 form 206 numbers by inclusion-exclusion: 140+93+56−46−28−18+9. Among the multiples of 7, exactly ten are not already counted: 7,49,77,91,119,133,161,203,217,259. Hence A has 216 elements.