0
$\begingroup$

I am asked:

Prove that if n+1 distinct numbers are selected from the first 2n positive integers {1,2,3,...,2n-1,2n} then at least two of the n+1 numbers are co-prime where n is a positive integer

I know 32 divides evenly into 64 and 96, but 32 is bigger than 16 and 20 so could not even divide. However 3+2=5 which can't get smaller.

How can I prove this?

  • 2
    It m$i$ght be e$a$sier to show that two of the num$b$ers $a$re $a$dj$a$cent.2012-11-13

1 Answers 1

2

Divide the set into n disjoint subsets as such:

{1,2},{3,4},{5,6},...,{2n-1,2n}

By the pegionhole principle, if you select n+1 numbers 2 of them must be in one of the above subsets. These 2 are coprime. (This is beacuse for all positive integers i,i+1 are coprime)