Difference between revisions of "2014 USAMO Problems/Problem 6"

m (Solution)
(Solution)
Line 2: Line 2:
 
Prove that there is a constant <math>c>0</math> with the following property: If <math>a, b, n</math> are positive integers such that <math>\gcd(a+i, b+j)>1</math> for all <math>i, j\in\{0, 1, \ldots n\}</math>, then<cmath>\min\{a, b\}>c^n\cdot n^{\frac{n}{2}}.</cmath>
 
Prove that there is a constant <math>c>0</math> with the following property: If <math>a, b, n</math> are positive integers such that <math>\gcd(a+i, b+j)>1</math> for all <math>i, j\in\{0, 1, \ldots n\}</math>, then<cmath>\min\{a, b\}>c^n\cdot n^{\frac{n}{2}}.</cmath>
  
==Solution==
+
The following solution is due to v_Enhance
Without loss of generality, let <math>a < b</math>.
+
Let <math>N = n+1</math> and assume <math>N</math> is (very) large. We construct an <math>N \times N</math> with cells <math>(i,j)</math> where <math>0 \le i, j \le n</math> and in each cell place a prime <math>p</math> dividing <math>\gcd (a+i, b+j)</math>.
  
Q.E.D.
+
The central claim is at least <math>50\%</math> of the primes in this table exceed <math>0.001n^2</math>. 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 <math>p \le 0.001n^2</math>.
 +
 
 +
Let <math>r = \pi(0.001n^2)</math> denote the number of such primes. Now we apply the three bounds: <cmath> \sum_p \frac{1}{p^2} < \frac 12 </cmath> which follows by adding all the primes directly with some computation, <cmath> \sum_p \frac 1p < \sum_{k=1}^r \frac 1k = O(\ln r) < o(N) </cmath> using the harmonic series bound, and <cmath> \sum_p 1 < r \sim O \left( \frac{N^2}{\ln N} \right) < o(N^2) </cmath> via Prime Number Theorem.  Hence the sum in question is certainly less than <math>\tfrac 12 N^2</math> for <math>N</math> large enough, establishing the central claim.
 +
 
 +
Hence some column <math>a+i</math> has at least one half of its primes greater than <math>0.001n^2</math>. Because this is greater than <math>n</math> for large <math>n</math>, these primes must all be distinct, so <math>a+i</math> exceeds their product, which is larger than <cmath> \left( 0.001n^2 \right)^{N/2} > c^n \cdot n^n </cmath> where <math>c</math> is some constant.

Revision as of 01:33, 9 April 2016

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}}.\]

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.