uniolympiads English

IMC 2023, Ημέρα 2, Θέμα 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}.

Πρωτότυπο από το επίσημο 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 .

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

(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.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 5. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;