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 v_Enhance

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.

Page

Toolbox

Search

2014 USAMO Problems/Problem 6

Problem

Solution