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{align*} |A|=&\left\lfloor\tfrac{280}{2}\right\rfloor+\left\lfloor\tfrac{280}{7}\right\rfloor+\left\lfloor\tfrac{280}{3}\right\rfloor+\left\lfloor\tfrac{280}{5}\right\rfloor\\ &-\left\lfloor\tfrac{280}{14}\right\rfloor-\left\lfloor\tfrac{280}{6}\right\rfloor-\left\lfloor\tfrac{280}{10}\right\rfloor-\left\lfloor\tfrac{280}{15}\right\rfloor-\left\lfloor\tfrac{280}{21}\right\rfloor-\left\lfloor\tfrac{280}{35}\right\rfloor\\ &+\left\lfloor\tfrac{280}{70}\right\rfloor+\left\lfloor\tfrac{280}{105}\right\rfloor+\left\lfloor\tfrac{280}{42}\right\rfloor+\left\lfloor\tfrac{280}{30}\right\rfloor\\ &-\left\lfloor\tfrac{280}{210}\right\rfloor \end{align*}
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\backslash X$) is at most $7$.
Now, consider the following eight sets
\begin{align} &\{2^2,3^2,5^2,7^2,13^2\}\\ &\{2\times31,3\times29,5\times23,7\times19,11\times17\}\\ &\{2\times47,3\times43,5\times41,7\times37,13\times19\}\\ &\{2\times41,3\times37,5\times31,7\times29,11\times23\}\\ &\{2\times23,3\times19,5\times17,7\times13,11^2\}\\ &\{2\times43,3\times41,5\times37,7\times31,13\times17\}\\ &\{2\times37,3\times31,5\times29,7\times23,11\times19\}\\ &\{2\times29,3\times23,5\times19,7\times17,11\times13\} \end{align}
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. $\square$
No comments:
Post a Comment