We prove the statement for any number $ j>1$ instead of $ 2$. It suffices to prove it for sufficiently large $ N$, as then we shall prove it also for smaller $ N$ by simply reducing $ c$ as much as we wish. Assume we have a set $ S$ of $ N$ numbers from $ [1;jN]$. For each $ x$ in $ S$ let $ n_{x}$ be the number of its divisors (including $ x$) greater than $ cN$. If we prove that $ \sum_{x\in S}n_{x}>jN$ then it is clear some number greater than $ cN$ will divide at least two numbers from $ S$, and they will form the desired pair. Let $ P$ be the set of primes. Let $ P=\{p_{1}<p_{2}<\ldots\}$. Let $ P_{i}=\{p_{i}<p_{i+m}<p_{i+2m}<\ldots\}$ where we have chosen $ m>j$. It is known that the product $ \prod_{p<k, p\in P}(1-\frac{1}{p})\sim \frac 1{ln(k)}$ (it follows from Mertens' Theorem). It is easy to deduce from here that $ \prod_{p<k, p\in P_{i}}(1-\frac{1}{p}) \sim \frac 1{\sqrt[m]{\ln(k)}}$. We denote $ a\sim b$ if $ |\ln(a)-\ln(b)|$ is bounded. Now pick up a number $ k$. The probability that a number less than $ jN$ is not divisible by any prime from $ P_{i}$ which is less than $ k$ is, as estimated above, at most $ C\frac 1{\sqrt[m]{\ln(k)}}$. Therefore we have at most $ \frac{CjN}{\sqrt[m]{\ln (k)}}$ numbers which have at most $ m$ prime divisors less than $ k$. We also can have at most $ ckN$ numbers less than $ ckN$. So per total, we have at most $ sN$ numbers which either are smaller than $ ckN$ or have at most $ m$ divisors less than $ k$. ($ s=ck+\frac{CjN}{\sqrt[m]{\ln (k)}}$) . Of the remaining at least $ (1-s)N$ numbers, each of them has at least $ m$ divisors greater than $ cN$ (just divide it by each of its prime divisors less than $ k$). So $ \sum_{x\in S}n_{x}>m(1-s)N$. It remains to show that $ m(1-s)N>jN$ or that $ s<1-\frac{j}{m}$. Now $ 1-\frac{j}{m}$ is some positive constant. Therefore we can select $ k$ sufficiently big such that $ \frac{Cj}{\sqrt[m]{\ln(k)}}$ is smaller than it. Hence we can now select $ c$ sufficiently small such that the additional terms $ ck$ is negligible, i.e. $ ck<1-\frac{j}{m}-\frac{Cj}{\sqrt[m]{k}}$ and we are done. Note: we do not need Mertens Theorem here. All we need is that the probability that a number has at most $ m$ prime divisors less than $ k$ tends to 0 as $ k$ tends to infinity. This can be proven also like this: Let $ p_{1}<p_{2}<\ldots<p_{r}<k$ be all the prime numbers less than $ k$. The probability that a number is divisible by some $ h$ of them $ q_{1}, q_{2}, \ldots, q_{h}$ where $ h<m$ is $ \prod_{i=1}^{h}\frac 1{q_{i}-1}Q$ where $ Q=\prod_{i=1}^{r}(1-\frac 1{p_{i}-1})$. Therefore the needed probability is at most $ Q\sum_{h<k}\sum_{(q_{1},q_{2},\ldots,q_{h})}\prod_{i=1}^{h}\frac 1{q_{i}-1}<Q\sum_{h<m}(\sum_{i=1}^{r}\frac 1{p_{i}-1})^{h}$. Now we can prove that is $ s=\sum_{i=1}^{r}\frac 1{p_{i}-1}$ then $ Q\sim e^{-s}$ and $ \lim_{k\to \infty}s= \infty$ therefore the probability clearly tends to $ 0$. Another, simpler proof of this fact goes as follows: since $ \prod_{p\in P}(1-\frac{1}{p})=0$ we deduce that for every $ \epsilon<0$ and $ i\in N$ there exists $ f(i)\in N, f(i)>i$ such that $ \prod_{j=i+1}^{f(i)}(1-\frac 1{p_{i}})<\frac{\epsilon}{m}$. Therefore if we take $ a_{1}=1$ and $ a_{i}=f(a_{i-1}-1)+1$ then we can find $ m$ groups of primes $ P_{i}=(p_{a_{i}},p_{a_{i}+1}, \ldots, p_{a_{i+1}-1})$ such that the probability that $ n$ is not divisible by neither of members of $ P_{i}$ is less than $ \frac{\epsilon}m$. Therefore the probability that $ n$ is divisible by a prime from each of the $ P_{i}$ is greater than $ 1-\epsilon$. Taking $ k>p_{a_{m}}$ and taking $ \epsilon\to 0$ we obtain the result.

While reading theis solution, I've been hoping that Riemann Conjecture appears somewhere as a lemma. Actually, it may be done much easier (let me prove also for numbers from 1 to jN instead from 1 to 2N): find such positive x, that the $ \prod_{4j<p<x}(1-1/p)<1/(2j)$. Then for large $ N$, at most $ N/2$ of numbers between 1 and $ 2N$ have not a divisor between $ 4j$ and $ x$. So, at least $ N/2$ of our numbers have a divisor between $ 4j$ and $ x$. Call such numbers nice. At least $ N/3$ nice numbers are greater than $ N/6$. Call such nice numbers beautiful. Divide every beautiful number by its divisor between $ 4j$ and $ x$. We get at least $ N/3$ ratios, which are between $ N/(6x)$ and $ N/4$. So, some two of them coincide and we get a desired pair.

Fedor Petrov wrote: Then for large $ N$, at most $ N/2$ of numbers between 1 and $ 2N$ have not a divisor between $ 4j$ and $ x$. Fedor Petrov wrote: At least $ N/3$ nice numbers are greater than $ N/6$. Can somebody help explain each of these statements? I am too stupid to see why...

Can anybody?

Quote: Then for large $ N$, at most $ N/2$ of numbers between 1 and $ 2N$ have not a divisor between $ 4j$ and $ x$. Because the density of numbers, having no divisor from $ 4j$ to $ x$ equals $ c=\prod_{4j<p<x} (1-1/p)$. That is, for large $ N$, there exist $ cN+O(1)$ numbers from $ [1,N]$ with this property. It follows from Chinese remainder theorem: if $ m=\prod_{4j<p<x} p$, then exactly $ cm$ remainders modulo $ m$ are accesible. Quote: At least $ N/3$ nice numbers are greater than $ N/6$. Because at most $ N/6$ of them are $ \le N/6$, other are $ >N/6$.

Very elegant problem! This falls prey to analytic estimates! oops, error

My sol is basically a generalisation of Fedor's. The probability that a number does not have a divisor $d$ such that $a<d<b$ is \[C(a,b)=\prod_{a<p<b}\bigg(1-\frac{1}{p}\bigg).\]Thus, for any large enough $N,$ at most $C(a,b)\cdot iN$ integers out of $\{1,2,...,iN\}$ do have any divisor $d$ such that $a<d<b.$ For a fixed $a,$ take $b$ such that $C(a,b)<1$. Then we can safely observe that at least $(1-C(a,b))\cdot iN$ positive integers out of our $N$ chosen ones have a divisor $d$ such that $a<d<b.$ We now divide those numbers by their divisor in the parameters in question. Take a $j$ big enough and observe that at least $(1-C(a,b)-1/j)\cdot iN$ numbers are greater than $N/j.$ Therefore, we have at least $(1-C(a,b)-1/j)\cdot iN$ ratios $r$ with the property \[\frac{N}{jb}\leq r\leq \frac{iN}{a}.\]Notice that if \[1-C(a,b)-\frac{1}{j}>\frac{i}{a}-\frac{1}{jb}\]then at least two of the ratios coincide and we have two numbers whose gcd is at least equal to $a.$ Just choose $a=N/\varepsilon$ and observe that it is enough to prove that \[1-C(a,b)>\frac{\varepsilon}{N}\]anf by taking $b$ in terms of $a$ such that $C(a,b)<\varepsilon$ we observe that for big enough $N$ the bound holds. Just make $\varepsilon$ smaller to prove that this works for all $N.$

oVlad wrote: My sol is basically a generalisation of Fedor's. The probability that a number does not have a divisor $d$ such that $a<d<b$ is \[C(a,b)=\prod_{a<p<b}\bigg(1-\frac{1}{p}\bigg).\]Thus, for any large enough $N,$ at most $C(a,b)\cdot iN$ integers out of $\{1,2,...,iN\}$ do have any divisor $d$ such that $a<d<b.$ For a fixed $a,$ take $b$ such that $C(a,b)<1$. Then we can safely observe that at least $(1-C(a,b))\cdot iN$ positive integers out of our $N$ chosen ones have a divisor $d$ such that $a<d<b.$ We now divide those numbers by their divisor in the parameters in question. Take a $j$ big enough and observe that at least $(1-C(a,b)-1/j)\cdot iN$ numbers are greater than $N/j.$ Therefore, we have at least $(1-C(a,b)-1/j)\cdot iN$ ratios $r$ with the property \[\frac{N}{jb}\leq r\leq \frac{iN}{a}.\]Notice that if \[1-C(a,b)-\frac{1}{j}>\frac{i}{a}-\frac{1}{jb}\]then at least two of the ratios coincide and we have two numbers whose gcd is at least equal to $a.$ Just choose $a=N/\varepsilon$ and observe that it is enough to prove that \[1-C(a,b)>\frac{\varepsilon}{N}\]anf by taking $b$ in terms of $a$ such that $C(a,b)<\varepsilon$ we observe that for big enough $N$ the bound holds. Just make $\varepsilon$ smaller to prove that this works for all $N.$ could you explain how we conclude from two of the ratios being equal that two numbers must have a gdc greater than a? Sorry.i'm a little dumb

Reviving my aops after a loooong time We prove the statement for all large enough values for $N$ say we have a contradictory set $S$. Parition $S$ into two sets . $S_1=\{x | x \in S , x\leq n\},S_2=\{x | x \in S , x>n\}$ \newline Claim: if we set $c$ small enough we can obtain a positive positive real constant $\delta$ such that $|S_2|<N(1-\delta)$. \newline Proof: say $c=\frac{1}{T}$ then we can set $T$ arbitarily large. Consider integer elements in the interval $[\frac{1}{T}N,\frac{1}{T-1}N)$ for each element $e$ in it define its multiplication class as the set $S_e=\{Te,(T+2)e\}$ and $S_e$ is always a subset of (N,2N] for large $T$. Claim: For large $T$ all the multiplication classes are disjoint. Proof: Otherwise the ratio of two elements in $[\frac{1}{T}N,\frac{1}{T-1}N]$ is $\frac{T+2}{T}$ but the ratio of any two elements in the interval is at max $\frac{T}{T-1}$. So $\frac{T+2}{T} \leq \frac{T}{T-1} \iff T^2+T-2 \leq T^2$ which dosent work for large $T$'s. From each multiplication class atleast one element is ignored and not present in $S_2$ otherwise we have contradiction. so atleast $\frac{N}{(T-1)T}+\mathcal{O}(1)$ elements in $(N,2N]$ are not present in $S_2$ giving the necessary $\delta$. Now let $p_i$ denote the $i$'th prime. Claim: For any positive real $E<1$ we can always find a positive integer $k$ such that there are atleast $NE$ elements in $S$ that are divisible by atleast one of $p_1,p_2,....,p_k$. Proof: Define $S_3=\{x|x \in S ,(x,p_1p_2....p_k)=1\}$ clearly $|S_3| \leq 2N \Pi_{i=1}^{i=k} (1-\frac{1}{p_i})$ Its well known that $$\Pi 1-\frac{1}{p_i}$$ gets arbitarily small. giving required result. Now choose $E$ really close to $1$ and let $p_1,p_2,...,p_k$ be the primes we get for that. Define $S_4=\{x | x > Ncp_k, x \in S,(x,p_1p_2.....p_k)>1\}$ clearly $|S_4| \geq N(E-cp_k)+\mathcal{O}(1)$ . for each element $e$ of $S_4$ define its friendship pair as the ordered pair $(N,\frac{N}{p_i})$ where $p_i$ is any of the first $k$ primes that divides. It is easy to see that all the friendship pairs are disjoint. When conatenated they produce atleast $N(2E-2cp_k)+\mathcal{O}(1)$ we finally contradict this!. Observe the second term in each ordered pair is at max $N$ so the total no of elements written in second position+ no of elements in first position that are in $S_1 \leq N$. And the no of elements in first position greater than $N$ gives at max $N(1-\delta)$ elements giving a max of $N(2-\delta)$ elements. so $2E-2cp_k \leq 2-\delta$ if we set $E$ sufficiently close to $1$ and set $c$ sufficiently small for that $E$ we have contradiction finishing the problem.