1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You used the pigeonhole principle when you argued that there would have to be $101$ numbers. $\endgroup$ – John Douma May 4 '20 at 3:00
2
$\begingroup$

Make the $50$ pigeonholes $$\{1,2\},\{3,4\},\dots,\{99,100\}$$ and use your observation that consecutive integers are relatively prime.

$\endgroup$
0
$\begingroup$

Try to find a set that contains no adjacent numbers. How large is the largest such set? Answer: $50$ elements... either the evens or the odds. Now add one more element...

$\endgroup$
0
$\begingroup$

Suppose $S$ is a subset of the natural numbers, and $|S|>50$. As you pointed out, if you can show that $S$ contains two neighbouring elements (i.e. if $k,k+1 \in S$ for some $k < 100$) then $S$ contains coprime elements. So define $[2n] = \{ 2n+1,2(n+1) \}$ for each $0 \leq n < 50$. Then $$ X = \{ [2n] \mid 0 \leq n < 50 \}$$ satisfies that $$ \bigcup X = \{ 1,2,\ldots,100 \} $$ and $|X| = 50$.

Define $$ f \colon S \rightarrow X $$ by $$ f(s) = [2n] \text{ if $s \in [2n]$}$$ This is well-defined. Since $|X| = 50 < 51 \leq |S|$, the pigeonhole-principle implies that $f$ is not injective; so there are $s,t \in S$ with $s \neq t$ such that $f[\{ s,t \}] = [2n]$ for some $n$, which proves the result.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.