2014 USAMO Problems/Problem 6
Prove that there is a constant with the following property: If are positive integers such that for all , then
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.