advanced pidgeon hole

[batteredbutnotdefeated]

Choose any (n+1) element subset from {1,2,3,..., 2n}. Show that this subset must contain two integers that are relatively prime.

[modularmarc101]

Solution

To ensure that there are elements that are coprime, we must have 2 consecutive positive integer elements. Consider the worst case scenario when choosing elements from the set: none of them are coprime. There are 2 such subsets: and . Adding another element to any of these sets will yield a pair of coprime elements.

[batteredbutnotdefeated]

True... But wouldn't you have to prove that there are no more than two subsets that have no coprime numbers?

[batteredbutnotdefeated]

After a while of thinking, I think I have come up with a more rigorous solution:

solution

Let an arbitrary integer q be any number in the set {1,2,3,...2n-1}. Then q+1 must be in the set {2,3,4,..., 2n}. We can pair each number q with it's partner q+1 to create n sets, each of which contain two relatively prime integers. Since we are asked to select a subset containing n+1 elements, all the elements must be from the n subsets we created. By the pidgeon-hole principle, two of those elements must of been in the same two-integer-relatively-prime subsets we created. Thus, they would be relatively prime.

[andersonw]

Unfortunately, there are 2n-1 sets ({1,2}, {2,3}, ..., {2n-1,2n}), not n sets, so your solution isn't quite right (unless if I am misunderstanding what you said), although the basic idea is pretty much correct.
Considering the n sets {1,2}, {3,4}, {5,6}, ..., {2n-1, 2n}, would work.

[batteredbutnotdefeated]

I think you have misunderstood . There are n sets because 2n/2 = n. each number q is paired with each number q+1, creating n sets.

[tenniskidperson3]

I think in his solution he meant to be and to be . With these sets, his solution works the way it's supposed to.

[Differ]

Induction makes for a very easy proof.