2014 USAMO Problems/Problem 6

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, \ldots n\}$, then\[\min\{a, b\}>c^n\cdot n^{\frac{n}{2}}.\]

Solution

The following solution is due to Gabriel Dospinescu and v_Enhance (also known as Evan Chen).

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 apply the three bounds: \[\sum_p \frac{1}{p^2} < \frac 12\] which follows by adding all the primes directly with some computation, \[\sum_p \frac 1p < \sum_{k=1}^r \frac 1k = O(\ln 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 $\tfrac 12 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.