Number theoryDifficulty 7.0National olympiad, round 2Prove itUkraine
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}, n≥1 be such a sequence. Name it sequence "consecutive" if for each positive integer number k and for any positive integer numbers n and m such that an<am, the following inequality holds: akn<akm. For example, the sequence an=n is "consecutive".
a) Prove that there exists a "consecutive" sequence which is different from an=n.
b) Does there exist a "consecutive" sequence for which the inequality an=n, n≥2 holds?
c) Does there exist a "consecutive" sequence for which the inequality an=n, n≥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=n. Let n=2α13α25α3…prαr be the unique representation of n as a product of primes, then the sequence {an}, an=2α23α15α3…prαr satisfies the statement of the problem.
Really, if n=2α13α25α3⋯prαrpr+10pr+20⋯, m=2β13β25β3⋯psβsps+10ps+20⋯, k=2γ13γ25γ3⋯ptγtpt+10pt+20⋯ and an<am, then akn<akm, as akn=2α2+γ23α1+γ15α3+γ3⋯pmax(r,t)αmax(r,t)+γmax(r,t)=akan, akm=2β2+γ23β1+γ15β3+γ3⋯pmax(s,t)βmax(s,t)+γmax(s,t)=akam and akn=akan<akam=akm. The constructed sequence is non-trivial, because a2=3, and is constructed using a permutation of the exponents of n in its prime factorization by means of shifting the exponents of two and three.
b. Next, let N(k)=⎩⎨⎧k−2,1,k+2,if k=4,6,8,…,if k=2,if k=1,3,5,… Then N(k1)=N(k2) if k1=k2. If now we construct a sequence in which for the number n represented as a product of primes, we shift the exponents of pk to pN(k), then the constructed sequence satisfies the statement of the problem. Really, let for n=2α13α25α37α4…pr−1αr−1prαr an=5α12α211α33α4⋯pN(r−1)αr−1pN(r)αr. Then the sequence {an} is "consecutive", because akn=akan and akn=akan<akam=akm.
Moreover, if n≥2 then an=n, because if an=n, then the following equalities hold: αN(k)=αk, αN(N(k))=αN(k)=αk, …, αN(...N(N(k)))=αk. But N(...N(N(k))) is unrestrictedly large beginning with some iteration, so if there exists nonzero αk in the prime factorization of n, then in its representation must exist nonzero powers of arbitrarily large prime numbers, which is a contradiction.
c. If for some sequence holds a1=1, then there exists l such that al=1. Then al<a1 and al2<al=1 — contradiction, because al2∈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.