USAMO

(by Titu Andreescu and Gabriel Dospinescu). Let $a, b, n$ be positive integers as in the statement of the problem. Let $P_n$ be the set of prime numbers not exceeding $n$. We will need the following

Lemma 1. There is a positive integer $n_0$ such that for all $n \ge n_0$ we have
$$\sum_{p \in P_n} \left( \frac{n}{p} + 1 \right)^2 < \frac{2}{3} n^2.$$

Proof. Expanding and dividing by $n^2$, and observing that $|P_n| \le n$, it suffices to prove the inequality
$$\sum_{p \in P_n} \frac{1}{p^2} + \frac{2}{n} \sum_{p \in P_n} \frac{1}{p} + \frac{1}{n} < \frac{2}{3}.$$
Since
$$\frac{2}{n} \sum_{p \in P_n} \frac{1}{p} < \frac{2}{n} \sum_{i=2}^n \frac{1}{i} < \frac{2}{n} \log n,$$
it suffices to prove the existence of a constant $r < \frac{2}{3}$ such that $\sum_{p \in P_n} \frac{1}{p^2} < r$. But
$$\begin{aligned} \sum_{p \in P_n} \frac{1}{p^2} & \le \frac{1}{4} + \frac{1}{9} + \sum_{k=1}^n \frac{1}{(2k+1)(2k+3)} \\ &= \frac{1}{4} + \frac{1}{9} + \sum_{k=1}^n \frac{1}{2} \left( \frac{1}{2k+1} - \frac{1}{2k+3} \right) \\ &= \frac{1}{4} + \frac{1}{9} + \frac{1}{2} \left( \frac{1}{3} - \frac{1}{2n+3} \right) < \frac{1}{4} + \frac{1}{9} + \frac{1}{6} < \frac{1}{3} \end{aligned}$$

From now on we fix such $n_0$, and we prove the statement assuming $n \ge n_0$. Note that for any $p \in P_n$ there are at most $\frac{n}{p} + 1$ numbers $i \in \{0, 1, \dots, n-1\}$ such that $p \mid a + i$, and likewise for $j \in \{0, 1, \dots, n-1\}$ such that $p \mid b + j$. Thus there are at most $\left(\frac{n}{p} + 1\right)^2$ pairs $(i, j)$ such that $p \mid \gcd(a + i, b + j)$. Using the previous lemma, we deduce that there are less than $\frac{2}{3}n^2$ pairs $(i, j)$ with $i, j \in \{0, 1, \dots, n-1\}$ such that $p \mid \gcd(a + i, b + j)$ for some $p \in P_n$.

Let $N$ be the least integer greater than or equal to $\frac{n^2}{3}$. By the above, there are at least $N$ pairs $(i, j)$ with $i, j \in \{0, 1, \dots, n-1\}$ such that $\gcd(a + i, b + j)$ is not divisible by any prime in $P_n$. Call these pairs $(i_s, j_s)$ for $s = 1, 2, \dots, N$. For each pair, choose a prime $p_s$ that divides $\gcd(a+i_s, b+j_s)$ (since, by hypothesis, $\gcd(a+i_s, b+j_s) > 1$); thus $p_s > n$. The map $s \mapsto p_s$ is injective, for if $p_s = p_{s'}$, then $p_s \mid i_s - i_{s'}$, implying $i_s = i_{s'}$, and similarly $j_s = j_{s'}$, hence $s = s'$.

We conclude that $\prod_{i=0}^{n-1} (a+i)$ is a multiple of $\prod_{s=1}^N p_s$. Since the $p_s$ are distinct prime numbers greater than $n$, then,
$$(a+n)^n > \prod_{i=0}^{n-1} (a+i) \ge \prod_{s=1}^N p_s \ge \prod_{i=1}^N (n+2i-1).$$
Let $X$ be this last product. Then
$$X^2 = \prod_{i=1}^N [(n+2i-1)(n+2(N+1-i)-1)] > \prod_{i=1}^N (2Nn) = (2Nn)^N,$$
where the inequality holds because
$$(n + 2i - 1)(n + 2(N + 1 - i) - 1) > n(2(N + 1 - i) - 1) + (2i - 1)n = 2Nn.$$
Finally
$$(a+n)^n > (2Nn)^{\frac{N}{2}} \ge \left(\frac{2n^3}{3}\right)^{\frac{n^2}{6}}.$$
Thus,
$$a \ge \left(\frac{2}{3}\right)^{\frac{1}{6} \cdot n} \cdot n^{\frac{n}{2}} - n,$$
which is larger than $c^n \cdot n^{\frac{n}{2}}$ when $n$ is large enough, for any constant $c < \left(\frac{2}{3}\right)^{\frac{1}{6}}$. Similarly, the same inequality holds for $b$.