Problem: Prove that there is a constant $c>0$ with the following property:
If $a$, $b$, $n$ are positive integers such that $\gcd(a+i, b+j)>1$
for all $i, j \in \{0, 1, \dots, n\}$, then
\[ \min\{a, b\}> (cn)^{n/2}. \]

\end{enumerate}

Solution: Let $N = n+1$ and assume $N$ is (very) large.
We construct an $N \times N$ with cells $(i,j)$
where $0 \le i, j \le n$ and in each cell
place a prime $p$ dividing $\gcd (a+i, b+j)$.

The central claim is at least $50\%$ of the primes
in this table exceed $0.001n^2$.
We count the maximum number of squares they could occupy:
\[
  \sum_p \left\lceil \frac{N}{p} \right\rceil^2
  \le \sum_p \left( \frac Np + 1 \right)^2
  = N^2 \sum_p \frac{1}{p^2} + 2N \sum_p \frac1p + \sum_p 1. \]
Here the summation runs over primes $p \le 0.001n^2$.

Let $r = \pi(0.001n^2)$ denote the number of such primes.
Now we consider the following three estimates.
First, \[ \sum_p \frac{1}{p^2} < \frac 12 \]
which follows by adding all the primes directly with some computation.
Moreover,
\[ \sum_p \frac 1p < \sum_{k=1}^r \frac 1k = O(\log r) < o(N) \]
using the harmonic series bound,
and \[ \sum_p 1 < r \sim O \left( \frac{N^2}{\ln N} \right) < o(N^2) \]
via Prime Number Theorem.
Hence the sum in question is certainly less than $\half N^2$ for $N$ large
enough, establishing the central claim.

Hence some column $a+i$ has at least one
half of its primes greater than $0.001n^2$.
Because this is greater than $n$ for large $n$,
these primes must all be distinct,
so $a+i$ exceeds their product,
which is larger than
\[ \left( 0.001n^2 \right)^{N/2} > c^n \cdot n^n \]
where $c$ is some constant (better than the requested bound).