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

Revision as of 00: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.

@@ 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>
-==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.

Page

Toolbox

Search

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

Revision as of 00:33, 9 April 2016

Problem