if you choose 51 numbers from the numbers 1-100 inclusive are you guaranteed to have two numbers which are coprime?
My thoughts are that you a have to look at the worst case scenarios e.g try to avoid picking coprime numbers for as long as possible so keep picking even numbers (50 of them) until you must pick an odd number which must be coprime with 2
does my reasoning work or is there a better method?
Best Answer
Yes, you're in the right track! But it isn't a very convincing argument. Mabye this is better: suppose you try not to pick consecutive numbers, since 1 is coprime to anything the smallest number you should pick is two, but if you don't pick consecutive number the next number you pick should always be at least two more than the last number. Doing this the last number is at least 102. This is impossible, we conclude we must pick two consecutive numbers.
Now suppose you pick consecutive numbers $n$ and $n+1$, these are coprime for if they weren't we would have $d|n,d|n+1$. but then $d$ would divide their difference, so $d|1$ in other words $d=1$.