uniolympiads English

IMC 2012, Ημέρα 2, Θέμα 3

Is the set of positive integers nn such that n!+1n! + 1 divides (2012n)!(2012n)! finite or infinite?

Πρωτότυπο από το επίσημο PDFIs the set of positive integers n such that n! + 1 divides (2012n)! finite or infinite?

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

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

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

Επίσημη λύση

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

Solution 1. Consider a positive integer nn with n!+1 ∣ (2012n)!n!+1\,\big|\,(2012n)!. It is well-known that for arbitrary nonnegative integers a1,…,aka_1,\ldots,a_k, the number (a1+…+ak)!(a_1+\ldots+a_k)! is divisible by a1!⋅…⋅ak!a_1!\cdot\ldots\cdot a_k!. (The number of sequences consisting of a1a_1 digits 11, …\ldots, aka_k digits kk, is (a1+…+ak)!a1!⋅…⋅ak!\frac{(a_1+\ldots+a_k)!}{a_1!\cdot\ldots\cdot a_k!}.) In particular, (n!)2012(n!)^{2012} divides (2012n)!(2012n)!.

Since n!+1n!+1 is co-prime with (n!)2012(n!)^{2012}, their product (n!+1)(n!)2012(n!+1)(n!)^{2012} also divides (2012n)!(2012n)!, and therefore

(n!+1)⋅(n!)2012≤(2012n)! .(n!+1)\cdot(n!)^{2012}\le(2012n)!\,.
By the known inequalities (n+1e)n<n!≤nn\left(\frac{n+1}{e}\right)^n<n!\le n^n, we get
(ne)2013n<(n!)2013<(n!+1)⋅(n!)2012≤(2012n)!<(2012n)2012nn<20122012e2013.\begin{gathered} \left(\frac{n}{e}\right)^{2013n}<(n!)^{2013}<(n!+1)\cdot(n!)^{2012}\le(2012n)!<(2012n)^{2012n}\\ n<2012^{2012}e^{2013}. \end{gathered}
Therefore, there are only finitely many such integers nn.

Remark. Instead of the estimate (n+1e)n<n!\left(\frac{n+1}{e}\right)^n<n!, we may apply the Multinomial theorem:

(x1+⋯+xℓ)N=∑k1+…+kℓ=NN!k1!⋅…⋅kℓ!x1k1…xℓkℓ.(x_1+\cdots+x_\ell)^N=\sum_{k_1+\ldots+k_\ell=N}\frac{N!}{k_1!\cdot\ldots\cdot k_\ell!}x_1^{k_1}\ldots x_\ell^{k_\ell}.
Applying this to N=2012nN=2012n, ℓ=2012\ell=2012 and x1=…=xℓ=1x_1=\ldots=x_\ell=1,
(2012n)!(n!)2012<(1+1+…+1⏟2012)2012n=20122012n,n!<n!+1≤(2012n)!(n!)2012<20122012n.\begin{gathered} \frac{(2012n)!}{(n!)^{2012}}<(\underbrace{1+1+\ldots+1}_{2012})^{2012n}=2012^{2012n},\\ n!<n!+1\le\frac{(2012n)!}{(n!)^{2012}}<2012^{2012n}. \end{gathered}
On the right-hand side we have a geometric progression which increases slower than the factorial on the left-hand side, so this is true only for finitely many nn.

Solution 2. Assume that n>2012n>2012 is an integer with n!+1 ∣ (2012n)!n!+1\,\big|\,(2012n)!. Notice that all prime divisors of n!+1n!+1 are greater than nn, and all prime divisors of (2012n)!(2012n)! are smaller than 2012n2012n.

Consider a prime pp with n<p<2012nn<p<2012n. Among 1,2,…,2012n1,2,\ldots,2012n there are [2012np]<2012\left[\frac{2012n}{p}\right]<2012 numbers divisible by pp; by p2>n2>2012np^2>n^2>2012n, none of them is divisible by p2p^2. Therefore, the exponent of pp in the prime factorization of (2012n)!(2012n)! is at most 2011. Hence,

n!+1=gcd⁡(n!+1,(2012n)!)<∏n<p<2012pp2011.n!+1=\gcd\big(n!+1,(2012n)!\big)<\prod_{n<p<2012p}p^{2011}.
Applying the inequality ∏p≤Xp<4X\prod\limits_{p\le X}p<4^X,
n!<∏n<p<2012pp2011<(∏p<2012np)2011<(42012n)2011=(42012⋅2011)n.(2)n!<\prod_{n<p<2012p}p^{2011}<\left(\prod_{p<2012n}p\right)^{2011}<\left(4^{2012n}\right)^{2011}=\left(4^{2012\cdot 2011}\right)^n. \tag{2}
Again, we have a factorial on the left-and side and a geometric progression on the right-hand side.

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

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

Πώς πήγε;