# Pigeonhole Principle for sets

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.

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.

• Doesn't the set of 25 integers you've given as an example contain elements that have a common divisor greater than 1? As 26 and 50 share 2 as a common divisor, so the example you've given for 25 wouldn't be possible, would it? – Artem Pulemotov May 28 at 3:42
• @JoshieBread Both 26,50 (since even) are in first set $S_1.$ – coffeemath May 28 at 4:51

Your set S contains 15 elements.

These 15 elements can be mapped to 15 classes C2, C3, C5,... C47, with each class Ci 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.

C2 would contain 2, 4, 6, ..., 48. C3 would contain 3, 6, 9, ..., 48.

I would satisfy the condition of having a common divisor more than one if I have two elements k1 and k2 from the same class Cjfor some prime number j.

Say I pick 3 and 6, both of these numbers are elements of C3. 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.