# Pigeon hole-proof

Printable View

• Feb 10th 2008, 11:37 PM
Severus
Pigeon hole-proof
You're supposed to show this with the pigeon hole principle.

Imagine the set {1, 2, ....., 2n}. Chose from this set n+1 different integers. Prove that there is always two integers among the chosen ones whose largest common divisor is 1.
• Feb 11th 2008, 12:18 AM
angel.white
Quote:

Originally Posted by Severus
You're supposed to show this with the pigeon hole principle.

Imagine the set {1, 2, ....., 2n}. Chose from this set n+1 different integers. Prove that there is always two integers among the chosen ones whose largest common divisor is 1.

Hmm, I'll give it a shot, but no promises :/

Since your set is {1, 2, 3, ... , 2n) You will have 2n elements.
Let us group every two elements together as such:
Set A = {{1,2}, {3,4}, {5,6} ... , {2n-1, 2n}}

Since each element in A contains consecutive integers, then if both integers from any element are chosen there will be two integers among the chosen which have a greatest common divisor of 1.

As there are 2 integers in each element, there are a total of n elements in this set. Then if you choose n integers, one integer may come from each element. So each element may have 1 integer selected from it. Since you are taking n+1 integers, you must take one more integer, however there are no more empty elements to choose from, so you must choose from one of the elements you have already drawn from. So because there are n elements in A, and you must choose n+1 integers, by the pigeonhole principle you must choose at least two from the same element.

Thus there will be at least two integers chosen which are consecutive, thus there will be two integers chosen who's greatest common divisor is one.
• Feb 11th 2008, 01:02 AM
Severus
Thank you, that was usefull. (Nod)