Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m (→‎Solution)
(→‎Solution)
 
(7 intermediate revisions by 4 users not shown)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
Without loss of generality, let <math>a < b</math>.
+
The following solution is due to Gabriel Dospinescu and v_Enhance (also known as Evan Chen).
−
Q.E.D.
+
 
 +
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>.
 +
 
 +
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:
 +
<cmath>
 +
\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.
 +
</cmath> 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.

Latest revision as of 10:55, 25 June 2020

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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2014_USAMO_Problems/Problem_6&oldid=126476"