SOLVED
Prove that, for any finite set $A\subset\mathbb{N}$, there exist $a,b\in A$ such that
\[\mathrm{gcd}(a,b)\leq a/\lvert A\rvert.\]
A conjecture of Graham
[Gr70], who also conjectured that (assuming $A$ itself has no common divisor) the only cases where equality is achieved are when $A=\{1,\ldots,n\}$ or $\{L/1,\ldots,L/n\}$ (where $L=\mathrm{lcm}(1,\ldots,n)$) or $\{2,3,4,6\}$.
Proved for all sufficiently large sets (including the sharper version which characterises the case of equality) independently by Szegedy [Sz86] and Zaharescu [Za87].
Proved for all sets by Balasubramanian and Soundararajan [BaSo96].
