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.