I am trying to solve the following problem, from the following collection of problems involving the pigeonhole principle: https://cemc.uwaterloo.ca/events/mathcircles/2018-19/Winter/Senior_Feb27.pdf – "Let S be a 51-element subset of {1, 2, ยทยทยท , 100}. Prove that I can find two numbers in S which are relatively prime."
What I've done so far is the following:
We know that if k is a number, then k+1 is relatively prime to k. So if I can show that there must be 2 numbers with a difference of 1 between them, then I can prove the above.
Let's then assume it's possible to create a subset of 51 numbers, such that the difference between each number is greater than 1. Let us then find the smallest maximum element of this subset. That means the number at the start of the set is 1, and the largest element would be 1+2(50), as there are 50 gaps between the 51 numbers of the subset. The smallest maximum element is 101, which is impossible as the largest element of the original set is 100. So there must be 2 numbers with a difference of 1.
However, I'm not sure how to use the pigeonhole principle to solve this problem – could someone give me some advice?
Thanks in advance.
Best Answer
Make the $50$ pigeonholes $$\{1,2\},\{3,4\},\dots,\{99,100\}$$ and use your observation that consecutive integers are relatively prime.