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.
In short, the proof such a set doesn't exist merely relies on the fact that any two consecutive integers are relatively prime.