Difference between revisions of "2014 USAMO Problems/Problem 6"
(→Solution) |
(→Problem) |
||
| 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> | ||
| − | The following solution is due to v_Enhance | + | ==Solution== |
| + | The following solution is due to [b]v_Enhance[/b] | ||
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>. | 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>. | ||
Revision as of 00:34, 9 April 2016
Problem
Prove that there is a constant 
with the following property: If 
are positive integers such that 
for all 
, then![\[\min\{a, b\}>c^n\cdot n^{\frac{n}{2}}.\]](http://latex.artofproblemsolving.com/0/2/b/02b7074a6db67693e1ca47702b4fe57d70147d3a.png)
Solution
The following solution is due to [b]v_Enhance[/b]
Let 
and assume 
is (very) large. We construct an 
with cells 
where 
and in each cell place a prime 
dividing 
.
The central claim is at least 
of the primes in this table exceed 
. 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 
.
Let 
denote the number of such primes. Now we apply the three bounds: ![\[\sum_p \frac{1}{p^2} < \frac 12\]](http://latex.artofproblemsolving.com/7/9/e/79ed4603fa4f0a1eaec19bce62dc49a5962903d9.png)
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)\]](http://latex.artofproblemsolving.com/8/f/6/8f6e72d6e93aee716739125f7752be4aeeeb9e45.png)
using the harmonic series bound, and ![\[\sum_p 1 < r \sim O \left( \frac{N^2}{\ln N} \right) < o(N^2)\]](http://latex.artofproblemsolving.com/5/3/d/53dc72482811ae3f73269339a30774204dae1ae9.png)
via Prime Number Theorem. Hence the sum in question is certainly less than 
for large enough, establishing the central claim.
Hence some column 
has at least one half of its primes greater than . Because this is greater than 
for large , these primes must all be distinct, so exceeds their product, which is larger than ![\[\left( 0.001n^2 \right)^{N/2} > c^n \cdot n^n\]](http://latex.artofproblemsolving.com/2/f/4/2f41fdc4a3e28a47399ccc5e8d20b339674ec6c2.png)
where 
is some constant.
