Another Beautiful Pigeon-Hole Argument

I first encountered this question in an assignment in our Graph Theory and Combinatorics course. Later, I also saw this in an MSE post and answered immediately. I was extremely happy to be able to solve this problem and now seems to be a good time to put it on this blog.

Problem Statement -

Let $S=\{1,2,\dots ,280\}$. Find the smallest natural number $n$ such that every $n$-element subset of $S$ contains $5$ pairwise relatively prime numbers.

Solution -

Before we begin with the real question, we note that $\lfloor \sqrt{280}\rfloor =16$. This means that all composite numbers below $280$ must have one prime factor in the set $\{2,3,5,7,11,13\}$. We will use this fact in our answer.

First, we will consider the subset $A$ of $S$ that only contains multiples of $2,3,5$ and $7$. We can use Principle of Inclusion and Exclusion to find the cardinality of $A$ as

$$\begin{array}{rl}|A|=& \lfloor \frac{280}{2}\rfloor +\lfloor \frac{280}{7}\rfloor +\lfloor \frac{280}{3}\rfloor +\lfloor \frac{280}{5}\rfloor \\ & -\lfloor \frac{280}{14}\rfloor -\lfloor \frac{280}{6}\rfloor -\lfloor \frac{280}{10}\rfloor -\lfloor \frac{280}{15}\rfloor -\lfloor \frac{280}{21}\rfloor -\lfloor \frac{280}{35}\rfloor \\ & +\lfloor \frac{280}{70}\rfloor +\lfloor \frac{280}{105}\rfloor +\lfloor \frac{280}{42}\rfloor +\lfloor \frac{280}{30}\rfloor \\ & -\lfloor \frac{280}{210}\rfloor \end{array}$$

which gives $|A|=216$.

Now, note that, $A$ only has multiples of four prime numbers. So, using Pigeon Hole Principle, we can say that any five elements of $A$ must have at least two multiples of a particular prime, which proves that any $5$ element subset of $A$ is NOT pairwise relatively prime.

This proves that if we want to have an $n$-element subset of $S$ such that any five of them will be relatively prime, then we must have $n>216$.

Now, notice that the cardinality of $A$ is $216$ and $A$ contains exactly $4$ prime numbers (namely, $2,3,5$ and $7$). So, the other $212$ numbers in $A$ (and hence in $S$) are composite.

Let us try to find the other composite numbers in $S$. These must be of the form $11m$ or $13n$ for some $m,n\in \mathbb{N}$ such that $m,n>10$ (since all multiples till $10$ have already been counted). It is easy to check that the only such composite numbers are  $121,143,169,187,209,221,247,253$. That gives precisely $8$ more composite numbers in $S$. So, $S$ has $220$ composite numbers and $59$ primes (with a $1$ which neither).

Now, consider a subset $X$ of $S$ such that $|X|=217$. We claim that there are five elements in $X$ such that any two of them are pairwise relatively prime. To prove that, let us assume on the contrary that our claim is false. So, any five element subset of $X$ must have two relatively non-prime elements. This forces the number of prime numbers in $X$ to be less than or equal to $4$ since if there are more than four prime numbers, then the set of these primes has all pairwise relatively prime numbers. So, there are at most four primes in $X$ which means that there are at least $213$ composite numbers in $X$. This means that the number of composite numbers outside $X$ (i.e., in $S\mathrm{\setminus }X$) is at most $7$.

Now, consider the following eight sets

$$\begin{array}{rl}& \{2^2,3^2,5^2,7^2,{13}^2\}\\ & \{2\times 31,3\times 29,5\times 23,7\times 19,11\times 17\}\\ & \{2\times 47,3\times 43,5\times 41,7\times 37,13\times 19\}\\ & \{2\times 41,3\times 37,5\times 31,7\times 29,11\times 23\}\\ & \{2\times 23,3\times 19,5\times 17,7\times 13,{11}^2\}\\ & \{2\times 43,3\times 41,5\times 37,7\times 31,13\times 17\}\\ & \{2\times 37,3\times 31,5\times 29,7\times 23,11\times 19\}\\ & \{2\times 29,3\times 23,5\times 19,7\times 17,11\times 13\}\end{array}$$

and note that the $40$ elements in these $8$ sets are all distinct because of the Unique Factorization Theorem. Also, since there are eight sets, and at most seven composite numbers can be outside $X$, by the Pigeon Hole Principle, at least one of these sets must be in $X$. Also, clearly, in all of the above sets, the elements are mutually co-prime.

This completes the proof. $◻$