Олимпиада Туймаада по математике. Старшая лига. 2007 год

Докажите, что существует такое положительное число $c$, что при любом натуральном $N$ среди любых $N$ натуральных чисел, не превосходящих $2N$, найдутся два числа, наибольший общий делитель которых больше $cN$. ( Ф. Петров )