Maths Olympiad Prep

Library / /38 of 48

Number theory Difficulty 8.9 Shortlist Prove it China

Given 20212021 distinct positive integers a1,a2,,a2021a_1, a_2, \dots, a_{2021}. Define the sequence {an}\{a_n\} inductively as follows: for each integer n2022n \ge 2022, ana_n is the smallest positive integer different from a1,a2,,an1a_1, a_2, \dots, a_{n-1} and not dividing the product an1an2an2021a_{n-1}a_{n-2}\dots a_{n-2021}. Prove: there exists a positive integer MM, such that all integers greater than or equal to MM appear in {an}\{a_n\}.

Solution

Let k=2021k=2021. In fact, we will prove the statement for any integer k>0k > 0.

Lemma 1 There exists C>0C > 0 independent of kk, such that τ(m)Cm1k+1\tau(m) \le C m^{\frac{1}{k+1}} holds for all positive integer mm, where τ(m)\tau(m) is the number of positive factors of mm.

Proof of lemma 1 Let m=p1α1p2α2prαrm = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_r^{\alpha_r} be the prime factorization of mm. Evidently,
τ(m)=(α1+1)(α2+1)(αr+1). \tau(m) = (\alpha_1 + 1)(\alpha_2 + 1)\dots(\alpha_r + 1).
Equivalently, there exists C>0C > 0 such that
i=1r(αi+1)k+1piαiCk+1 \prod_{i=1}^{r} \frac{(\alpha_i + 1)^{k+1}}{p_i^{\alpha_i}} \le C^{k+1}
holds for all prime pip_i and positive integers αi\alpha_i. Note that polynomials grow slower than exponential functions, and hence for each prime p2k+1p \le 2^{k+1}, the fraction (α+1)k+1pα\frac{(\alpha + 1)^{k+1}}{p^{\alpha}} has an upper bound when α0\alpha \ge 0. Since the number of primes p2k+1p \le 2^{k+1} is finite, there exists CC' such that for any prime p2k+1p \le 2^{k+1},
(α+1)k+1pα<C. \frac{(\alpha + 1)^{k+1}}{p^{\alpha}} < C'.
On the other hand, for p>2k+1p > 2^{k+1},
(α+1)k+1pα<(α+12α)k+1<1. \frac{(\alpha + 1)^{k+1}}{p^{\alpha}} < \left( \frac{\alpha + 1}{2^{\alpha}} \right)^{k+1} < 1.
It follows that i=1r(αi+1)k+1piαiCs\prod_{i=1}^{r} \frac{(\alpha_i + 1)^{k+1}}{p_i^{\alpha_i}} \le C'^s, where ss is the number of distinct prime factors of mm less than 2k+12^{k+1}. The existence of C>0C > 0 is now verified.

Lemma 2 For any fixed integer L>0L > 0, there exists M>0M > 0 such that for any positive integer mMm \ge M, one can find a prime power pαmp^\alpha|m, and pα>Lp^\alpha > L.

Proof of lemma 2 Consider all prime powers less than or equal to LL: there are only finitely many of them. Define MM equals the product of them plus 11. If mMm \ge M and pmp|m, then its highest power in mm satisfies pαmp^\alpha|m, and pα>Lp^\alpha > L.

Lemma 3 There exists a positive integer DD such that an<2n+Da_n < 2n + D for every positive integer nn.

Proof of Lemma 3 We take DD satisfying D>max1sk{as}D > \max_{1 \le s \le k}\{a_s\} and
D>2kCk+1+CDkk+1, D > 2^k C^{k+1} + C D^{\frac{k}{k+1}},
where C>0C > 0 is defined in Lemma 1, and use induction to prove an<2n+Da_n < 2n + D for every nn. By the choice of DD, an<2n+Da_n < 2n + D is true for n=1,2,,kn = 1, 2, \dots, k. Assume an<2n+Da_n < 2n + D holds for 1,2,,n+k11, 2, \dots, n + k - 1, where nn is a positive integer. Now for an+ka_{n+k}, it is known from the problem that an+ka_{n+k} is the smallest positive integer not dividing anan+1an+k1a_n a_{n+1} \dots a_{n+k-1}, and different from a1,,an+k1a_1, \dots, a_{n+k-1}. Hence,
an+kτ(anan+1an+k1)+n+k. a_{n+k} \le \tau(a_n a_{n+1} \dots a_{n+k-1}) + n + k.
From Lemma 1 and induction hypothesis, we have
an+kC(anan+1an+k1)1k+1+n+k<C(2(n+k1)+D)kk+1+n+k<C(2kk+1(n+k)kk+1+Dkk+1)+n+k. \begin{align*} a_{n+k} &\le C(a_n a_{n+1} \dots a_{n+k-1})^{\frac{1}{k+1}} + n + k \\ &< C(2(n+k-1) + D)^{\frac{k}{k+1}} + n + k \\ &< C(2^{\frac{k}{k+1}}(n+k)^{\frac{k}{k+1}} + D^{\frac{k}{k+1}}) + n + k. \end{align*}
In the last step, we use the fact that xkk+1x^{\frac{k}{k+1}} is concave down for x>0x > 0.

Now, if n+k2kCk+1n + k \le 2^k C^{k+1}, then
an+k<C2kk+1(n+k)kk+1+CDkk+1+n+k2kCk+1+CDkk+1+n+k<D+2(n+k); \begin{align*} a_{n+k} &< C 2^{\frac{k}{k+1}} (n+k)^{\frac{k}{k+1}} + C D^{\frac{k}{k+1}} + n + k \\ &\le 2^k C^{k+1} + C D^{\frac{k}{k+1}} + n + k \\ &< D + 2(n+k); \end{align*}
if n+k>2kCk+1n + k > 2^k C^{k+1}, then
C2kk+1(n+k)kk+1<n+k,CDkk+1<D, C 2^{\frac{k}{k+1}} (n + k)^{\frac{k}{k+1}} < n + k, \quad C D^{\frac{k}{k+1}} < D,
and
an+kn+k+D+n+k=2(n+k)+D. a_{n+k} \le n + k + D + n + k = 2(n + k) + D.
Therefore, an<2n+Da_n < 2n + D is true for n+kn + k.

Return to the original problem. For integer m>0m > 0, if mm does not appear in the sequence, then, as the elements in {an}\{a_n\} are distinct, there must exist a positive integer N1N_1, such that an>ma_n > m for n>N1n > N_1. By definition of {an}\{a_n\}, manan+1an+k1m|a_n a_{n+1} \dots a_{n+k-1} for all n>N1n > N_1.

According to Lemma 2, there exists M>0M > 0, such that for any integer mMm \ge M, we can find a prime power pαmp^\alpha|m, and pα>(3k)kp^\alpha > (3k)^k. We claim that such mm must appear in {an}\{a_n\}. Suppose to the contrary that for some m>Mm > M, mm does not appear in {an}\{a_n\}. Fix a prime power pαmp^\alpha|m, pα>(3k)kp^\alpha > (3k)^k. By the previous argument, there exists a positive integer N1N_1, such that for n>N1n > N_1,
manan+1an+k1. m|a_n a_{n+1} \dots a_{n+k-1}.
For this nn, there exists ii, nin+k1n \le i \le n + k - 1 and pα/kaip^{\lceil \alpha/k \rceil} | a_i. Let
N2>3N1+D+3k, N_2 > 3N_1 + D + 3k,
and consider the set A={n:1nN2,pα/kan}A = \{n : 1 \le n \le N_2, p^{\lceil \alpha/k \rceil} |a_n\}. On one hand, from Lemma 3, we have an<2N2+Da_n < 2N_2 + D, and thus
A2N2+Dpαk<2N2+D3k. |A| \le \frac{2N_2 + D}{p^{\lceil \frac{\alpha}{k} \rceil}} < \frac{2N_2 + D}{3k}.
On the other hand, since mm does not appear in {an}\{a_n\}, manan+1an+k1m|a_n a_{n+1}\dots a_{n+k-1} for n>N1n > N_1. Consequently, for any kk consecutive terms in {N1+1,N1+2,,N2}\{N_1 + 1, N_1 + 2, \dots, N_2\}, at least one term belongs to AA, implying that AN2N1k1|A| \ge \frac{N_2 - N_1}{k} - 1. However, by the choice of N2N_2, we have
AN2N1k1>2N2+D3k, |A| \ge \frac{N_2 - N_1}{k} - 1 > \frac{2N_2 + D}{3k},
which contradicts the previous estimate. This means all integers mMm \ge M must appear in {an}\{a_n\}. \Box

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.