Difference between revisions of "2014 USAMO Problems/Problem 6"
(→Solution) |
(→Solution) |
||
(3 intermediate revisions by 2 users not shown) | |||
Line 3: | Line 3: | ||
==Solution== | ==Solution== | ||
− | The following solution is due to v_Enhance | + | The following solution is due to Gabriel Dospinescu and v_Enhance (also known as Evan Chen). |
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>. | ||
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: | 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 | \sum_p \left\lceil \frac{N}{p} \right\rceil^2 | ||
\le \sum_p \left( \frac Np + 1 \right)^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. | = 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. | 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. | 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 11:55, 25 June 2020
Problem
Prove that there is a constant with the following property: If
are positive integers such that
for all
, then
Solution
The following solution is due to Gabriel Dospinescu and v_Enhance (also known as Evan Chen).
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:
Here the summation runs over primes
.
Let denote the number of such primes. Now we apply the three bounds:
which follows by adding all the primes directly with some computation,
using the harmonic series bound, and
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
where
is some constant.