Problem 3

Let

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 2 of 5: Use the four prime divisors to rule out five

Previous step Next step

|A|=216\ \Longrightarrow\ A\text{ has no five pairwise coprime elements}

Detailed analysis

Every member of A is divisible by at least one of 2,3,5,7. If five members were pairwise relatively prime, these four primes would have to be assigned to five different members, impossible by the pigeonhole principle. Thus any valid n is at least 217.