uniolympiads Ελληνικά

IMC 2023, Day 2, Problem 10

For every positive integer nn, let f(n),g(n)f(n), g(n) be the minimal positive integers such that

1+11!+12!+⋯+1n!=f(n)g(n).1 + \frac{1}{1!} + \frac{1}{2!} + \dots + \frac{1}{n!} = \frac{f(n)}{g(n)}.

Determine whether there exists a positive integer nn for which g(n)>n0.999ng(n) > n^{0.999n}.

Original from the official PDFFor every positive integer n, let f (n), g(n) be the minimal positive integers such that 1 1 1 f (n) 1 + + + ... + = . 1! 2! n! g(n) Determine whether there exists a positive integer n for which g(n) > n 0.999 n .

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(proposed by Fedor Petrov, St. Petersburg State University)

Solution. We show that there does exist such a number nn.

Let ε=10−10\varepsilon = 10^{-10}. Call a prime pp special, if for certain k∈{1,2,…,p−1}k \in \{1,2,\dots,p-1\} there exist at least ε⋅k\varepsilon\cdot k positive integers j≤kj \le k for which pp divides f(j)f(j).

Lemma. There exist only finitely many special primes.

Proof. Let pp be a special prime number, and pp divides f(j)f(j) for at least ε⋅k\varepsilon\cdot k values of j∈{1,2,…,k}j \in \{1,2,\dots,k\}. Note that if pp divides f(j)f(j) and f(j+r)f(j+r), then pp divides

(j+r)!(f(j+r)g(j+r)−f(j)g(j))=1+(j+r)+(j+r)(j+r−1)+…+(j+r)…(j+2)(j+r)!\left(\frac{f(j+r)}{g(j+r)} - \frac{f(j)}{g(j)}\right) = 1 + (j+r) + (j+r)(j+r-1) + \ldots + (j+r)\ldots(j+2)
that is a polynomial of degree r−1r-1 with respect to jj. Thus, for fixed jj it equals to 00 modulo pp for at most r−1r-1 values of jj. Look at our ≥ε⋅k\ge \varepsilon\cdot k values of j∈{1,2,…,k}j \in \{1,2,\dots,k\} and consider the gaps between consecutive jj's. The number of such gaps which are greater than 2/ε2/\varepsilon does not exceed ε⋅k/2\varepsilon\cdot k/2 (since the total sum of gaps is less than kk). Therefore, at least ε⋅k/2−1\varepsilon\cdot k/2 - 1 gaps are at most 2/ε2/\varepsilon. But the number of such small gaps is bounded from above by a constant (not depending on kk) by the above observation. Therefore, kk is bounded, and, since pp divides f(1)f(2)…f(k)f(1)f(2)\ldots f(k), pp is bounded too.

Now we want to bound the product g(1)g(2)…g(n)g(1)g(2)\ldots g(n) (for a large integer nn) from below. Let p≤np \le 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)\nu_p\bigl(g(1)g(2)\ldots g(n)\bigr) \ge (1-\varepsilon)\nu_p(1!\cdot 2!\cdot \ldots \cdot n!) \tag{1}

Partition the numbers p,p+1,…,np, p+1, \dots, n onto the intervals of length pp (except possibly the last interval which may be shorter): {p,p+1,…,2p−1}\{p, p+1, \dots, 2p-1\}, …\dots, {p⌊n/p⌋,…,n}\{p\lfloor n/p\rfloor, \dots, n\}. Note that in every interval Δ=[a⋅p,a⋅p+k]\Delta = [a\cdot p, a\cdot p + k], all factorials x!x! with x∈Δx \in \Delta have the same pp-adic valuation, denote it T=νp((ap)!)T = \nu_p\bigl((ap)!\bigr). We claim that at least (1−ε)(k+1)(1-\varepsilon)(k+1) valuations of g(x)g(x), x∈Δx \in \Delta, are equal to the same number TT. Indeed, if j=0j = 0 or 1≤j≤k1 \le j \le k and f(j)f(j) is not divisible by pp, then

1(ap)!+1(ap+1)!+…+1(ap+j)!=1(ap)!⋅AB\frac{1}{(ap)!} + \frac{1}{(ap+1)!} + \ldots + \frac{1}{(ap+j)!} = \frac{1}{(ap)!}\cdot\frac{A}{B}
where A≡f(j)(modp)A \equiv f(j) \pmod p, B≡g(j)(modp)B \equiv g(j) \pmod p, so, this sum has the same pp-adic valuation as 1/(ap)!1/(ap)!, which is strictly less than that of the sum ∑i=0ap−11/i!\sum_{i=0}^{ap-1} 1/i!, that yields νp(g(ap+j))=νp((ap)!)\nu_p\bigl(g(ap+j)\bigr) = \nu_p\bigl((ap)!\bigr). Using this for every segment Δ\Delta, we get (1).

Now, using (1) for all non-special primes, we get

A⋅g(1)g(2)…g(n)≥(1!⋅2!⋅…⋅n!)1−ε,A\cdot g(1)g(2)\ldots g(n) \ge (1!\cdot 2!\cdot \ldots \cdot n!)^{1-\varepsilon},
where A=∏p,kpνp(g(k))A = \prod_{p,k} p^{\nu_p(g(k))}, pp runs over non-special primes, kk from 11 to nn. Since νp(g(k))≤νp(k!)=∑i=1∞⌊k/pi⌋≤k\nu_p(g(k)) \le \nu_p(k!) = \sum_{i=1}^{\infty}\lfloor k/p^i\rfloor \le k, we get
A≤(∏pp)1+2+…+n≤Cn2A \le (\prod_p p)^{1+2+\ldots+n} \le C^{n^2}
for some constant CC. But if we had g(n)≤n0.999n≤enn!0.999g(n) \le n^{0.999n} \le e^n n!^{0.999} for all nn, then
log⁡(A⋅g(1)g(2)…g(n))≤O(n2)+0.999log⁡(1!⋅2!⋅…⋅n!)<(1−ε)log⁡(1!⋅2!⋅…⋅n!)\log\bigl(A\cdot g(1)g(2)\ldots g(n)\bigr) \le O(n^2) + 0.999\log(1!\cdot 2!\cdot \ldots \cdot n!) < (1-\varepsilon)\log(1!\cdot 2!\cdot \ldots \cdot n!)
for large nn, 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.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?