USAMO 2014 — Days 1 and 2 Question 6

Prove that a constant $c>0$ exists such that, whenever positive integers $a,b,n$ satisfy $\gcd(a+i,b+j)>1$ for every $i,j\in\{0,1,\ldots,n\}$, one has
$$\min\{a,b\}>(cn)^{n/2}.$$

Proposed by Gabriel Dospinescu (as credited in the supplied compilation).