# Pigeon Hole Principle (most probably)

Prove that any set of 46 distinct 2-digit numbers contains two distinct numbers which are relatively prime.

This is what I am trying to prove. I have a feeling that it would be using the pigeon hole principle but I just cannot figure it out. This is what I found interesting so far: There are 90 2-digits numbers ([10,99]), which means that there are exactly 45 even numbers, which means that in a set with 46 numbers, there must be at least one odd number. Though I do not know what to make of that... Also, 46 is optimal, in the snse that there exists a set of 45 distinct 2-digit numbers so that no two distinct numbers are relatively prime.

Suppose by contradiction that $$S$$ is a set of $$46$$ integers in $$\{10, \ldots, 99\}$$ such that no two distinct elements $$a, b \in S$$ are relatively prime; i.e., for all $$a, b \in S$$ such that $$a \ne b$$, $$\gcd(a,b) > 1$$.
A few key observations are needed. First is that if $$b = a+1$$, then $$\gcd(a,b) = 1$$. So $$S$$ cannot contain any consecutive elements. Second, what is the maximal size of the set $$S$$ under this condition? Since there are $$99 - 10 + 1 = 90$$ two-digit numbers, one can choose at most half, or $$45$$ of these numbers in such a way that there are no two consecutive elements. But this contradicts the assumption that $$|S| = 46$$; therefore, no such $$S$$ exists.