Maths Olympiad Prep

Library / /37 of 39

Number theory Difficulty 7.0 National olympiad, round 2 Prove it Ukraine

Consider the infinite sequences of positive integer numbers, in which each positive integer number to meet among elements of this sequence is equal once. Let {an}\{a_n\}, n1n \ge 1 be such a sequence. Name it sequence "consecutive" if for each positive integer number kk and for any positive integer numbers nn and mm such that an<ama_n < a_m, the following inequality holds: akn<akma_{kn} < a_{km}. For example, the sequence an=na_n = n is "consecutive".

a) Prove that there exists a "consecutive" sequence which is different from an=na_n = n.

b) Does there exist a "consecutive" sequence for which the inequality anna_n \neq n, n2n \geq 2 holds?

c) Does there exist a "consecutive" sequence for which the inequality anna_n \neq n, n1n \geq 1 holds?

Solution

Answer: b) such sequence exists; c) such sequence doesn't exist.

a. Show the example of such a "consecutive" sequence which is different from an=na_n = n. Let n=2α13α25α3prαrn = 2^{\alpha_1}3^{\alpha_2}5^{\alpha_3}\dots p_r^{\alpha_r} be the unique representation of nn as a product of primes, then the sequence {an}\{a_n\}, an=2α23α15α3prαra_n = 2^{\alpha_2}3^{\alpha_1}5^{\alpha_3}\dots p_r^{\alpha_r} satisfies the statement of the problem.

Really, if n=2α13α25α3prαrpr+10pr+20n = 2^{\alpha_1}3^{\alpha_2}5^{\alpha_3}\cdots p_r^{\alpha_r}p_{r+1}^0p_{r+2}^0\cdots, m=2β13β25β3psβsps+10ps+20m = 2^{\beta_1}3^{\beta_2}5^{\beta_3}\cdots p_s^{\beta_s}p_{s+1}^0p_{s+2}^0\cdots, k=2γ13γ25γ3ptγtpt+10pt+20k = 2^{\gamma_1}3^{\gamma_2}5^{\gamma_3}\cdots p_t^{\gamma_t}p_{t+1}^0p_{t+2}^0\cdots and an<ama_n < a_m, then akn<akma_{kn} < a_{km}, as
akn=2α2+γ23α1+γ15α3+γ3pmax(r,t)αmax(r,t)+γmax(r,t)=akan, a_{kn} = 2^{\alpha_2+\gamma_2} 3^{\alpha_1+\gamma_1} 5^{\alpha_3+\gamma_3} \cdots p_{\max(r,t)}^{\alpha_{\max(r,t)}+\gamma_{\max(r,t)}} = a_k a_n,
akm=2β2+γ23β1+γ15β3+γ3pmax(s,t)βmax(s,t)+γmax(s,t)=akam a_{km} = 2^{\beta_2 + \gamma_2} 3^{\beta_1 + \gamma_1} 5^{\beta_3 + \gamma_3} \cdots p_{\max(s,t)}^{\beta_{\max(s,t)} + \gamma_{\max(s,t)}} = a_k a_m
and akn=akan<akam=akma_{kn} = a_k a_n < a_k a_m = a_{km}. The constructed sequence is non-trivial, because a2=3a_2 = 3, and is constructed using a permutation of the exponents of nn in its prime factorization by means of shifting the exponents of two and three.

b. Next, let
N(k)={k2,if k=4,6,8,,1,if k=2,k+2,if k=1,3,5, N(k) = \begin{cases} k-2, & \text{if } k = 4, 6, 8, \dots, \\ 1, & \text{if } k = 2, \\ k+2, & \text{if } k = 1, 3, 5, \dots \end{cases}
Then N(k1)N(k2)N(k_1) \neq N(k_2) if k1k2k_1 \neq k_2. If now we construct a sequence in which for the number nn represented as a product of primes, we shift the exponents of pkp_k to pN(k)p_{N(k)}, then the constructed sequence satisfies the statement of the problem. Really, let for n=2α13α25α37α4pr1αr1prαrn = 2^{\alpha_1}3^{\alpha_2}5^{\alpha_3}7^{\alpha_4}\dots p_{r-1}^{\alpha_{r-1}}p_r^{\alpha_r}
an=5α12α211α33α4pN(r1)αr1pN(r)αr. a_n = 5^{\alpha_1} 2^{\alpha_2} 11^{\alpha_3} 3^{\alpha_4} \cdots p_{N(r-1)}^{\alpha_{r-1}} p_{N(r)}^{\alpha_r}.
Then the sequence {an}\{a_n\} is "consecutive", because akn=akana_{kn} = a_k a_n and akn=akan<akam=akma_{kn} = a_k a_n < a_k a_m = a_{km}.

Moreover, if n2n \ge 2 then anna_n \ne n, because if an=na_n = n, then the following equalities hold: αN(k)=αk\alpha_{N(k)} = \alpha_k, αN(N(k))=αN(k)=αk\alpha_{N(N(k))} = \alpha_{N(k)} = \alpha_k, \dots, αN(...N(N(k)))=αk\alpha_{N(...N(N(k)))} = \alpha_k. But N(...N(N(k)))N(...N(N(k))) is unrestrictedly large beginning with some iteration, so if there exists nonzero αk\alpha_k in the prime factorization of nn, then in its representation must exist nonzero powers of arbitrarily large prime numbers, which is a contradiction.

c. If for some sequence holds a11a_1 \neq 1, then there exists ll such that al=1a_l = 1. Then al<a1a_l < a_1 and al2<al=1a_{l2} < a_l = 1 — contradiction, because al2Na_{l2} \in \mathbb{N}.

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 and solution reproduced as published; topic and difficulty added by this site.