(proposed by Fedor Petrov, St. Petersburg State University)
Solution. We show that there does exist such a number n.
Let ε=10−10. Call a prime p special, if for certain k∈{1,2,…,p−1} there exist at least ε⋅k positive integers j≤k for which p divides f(j).
Lemma. There exist only finitely many special primes.
Proof. Let p be a special prime number, and p divides f(j) for at least ε⋅k values of j∈{1,2,…,k}. Note that if p divides f(j) and f(j+r), then p divides
(j+r)!(g(j+r)f(j+r)−g(j)f(j))=1+(j+r)+(j+r)(j+r−1)+…+(j+r)…(j+2)
that is a polynomial of degree
r−1 with respect to
j. Thus, for fixed
j it equals to
0 modulo
p for at most
r−1 values of
j. Look at our
≥ε⋅k values of
j∈{1,2,…,k} and consider the gaps between consecutive
j's. The number of such gaps which are greater than
2/ε does not exceed
ε⋅k/2 (since the total sum of gaps is less than
k). Therefore, at least
ε⋅k/2−1 gaps are at most
2/ε. But the number of such small gaps is bounded from above by a constant (not depending on
k) by the above observation. Therefore,
k is bounded, and, since
p divides
f(1)f(2)…f(k),
p is bounded too.
Now we want to bound the product g(1)g(2)…g(n) (for a large integer n) from below. Let p≤n be a non-special prime. Our nearest goal is to prove that
νp(g(1)g(2)…g(n))≥(1−ε)νp(1!⋅2!⋅…⋅n!)(1)
Partition the numbers p,p+1,…,n onto the intervals of length p (except possibly the last interval which may be shorter): {p,p+1,…,2p−1}, …, {p⌊n/p⌋,…,n}. Note that in every interval Δ=[a⋅p,a⋅p+k], all factorials x! with x∈Δ have the same p-adic valuation, denote it T=νp((ap)!). We claim that at least (1−ε)(k+1) valuations of g(x), x∈Δ, are equal to the same number T. Indeed, if j=0 or 1≤j≤k and f(j) is not divisible by p, then
(ap)!1+(ap+1)!1+…+(ap+j)!1=(ap)!1⋅BA
where
A≡f(j)(modp),
B≡g(j)(modp), so, this sum has the same
p-adic valuation as
1/(ap)!, which is strictly less than that of the sum
∑i=0ap−11/i!, that yields
νp(g(ap+j))=νp((ap)!). Using this for every segment
Δ, we get (1).
Now, using (1) for all non-special primes, we get
A⋅g(1)g(2)…g(n)≥(1!⋅2!⋅…⋅n!)1−ε,
where
A=∏p,kpνp(g(k)),
p runs over non-special primes,
k from
1 to
n. Since
νp(g(k))≤νp(k!)=∑i=1∞⌊k/pi⌋≤k, we get
A≤(p∏p)1+2+…+n≤Cn2
for some constant
C. But if we had
g(n)≤n0.999n≤enn!0.999 for all
n, then
log(A⋅g(1)g(2)…g(n))≤O(n2)+0.999log(1!⋅2!⋅…⋅n!)<(1−ε)log(1!⋅2!⋅…⋅n!)
for large
n, a contradiction.
Transcribed from the official solutions, page 5. This transcription has not been checked a second time; if in doubt, look at the original.