Pigeonhole Principle for sets

Question

I have been asked to answer the following question;

Let A = {2,3, ..., 50}, that is A is the set of positive integers greater than 1 and less than 51. Determine the smallest number $x$ such that every subset of A having $x$ elements contains at least two integers that have a common divisor greater than 1, and justify your answer.

My attempt at the solution is by defining a set; $$S=[s\in A |s\in primes]$$ This defines the set containing 15 integers with no 2 primes containing a common divisor greater than one divisible by 1 and themselves. Thus, $x>15.$
Now I thought of taking; $$P=[p|p\in primes]$$ And then continue by partitioning this set into 15 subsets. But I'm not too sure where to go from here.

Any help would be greatly appreciated.

Answer 1

The answer is 16: to show that 15 is possible, just take $2,3,5,7,\ldots,47$.

Now for the fun part, making the pigeonholes. The first pigeonhole is $$S_1=\{2,4,6,8,\ldots\}$$ and the second is $$S_2=\{3,9,15,\ldots\}$$ Continuing thus, the $i$th set is (for $i>1$) $$S_i=\{p_i,\ldots\}$$ where $p_i$ is the $i$th prime, and the elements that occur in the set are multiples of $p_i$ which don't occur in previous sets.

Note that every positive integer ends up in one of these sets; in particular, the numbers 2-50 end up in the first 15 of these sets. Thus taking $16$ numbers guarantees two in the same set (by PHP) and we're done, since any two numbers in a set trivially share a factor.

Answer 2

Your set S contains 15 elements.

These 15 elements can be mapped to 15 classes C₂, C₃, C₅,... C₄₇, with each class C_i containing all the elements in S which are divisible by i.

Every number in S can be decomposed to its unique prime factorisation, and we can form our classes. Note that the classes here need not be (and are not) mutually exclusive.

C₂ would contain 2, 4, 6, ..., 48. C₃ would contain 3, 6, 9, ..., 48.

I would satisfy the condition of having a common divisor more than one if I have two elements k₁ and k₂ from the same class C_jfor some prime number j.

Say I pick 3 and 6, both of these numbers are elements of C₃. I have a common divisor of 3 > 1.

Since there are 15 class (pigeonholes) and we want two elements from the same class, then we need 15 + 1 = 16 elements from S.