Number theoryDifficulty 5.9AIME, harderProve itMongolia
Let A be a nonempty subset of the positive integers. If x∈A, then [3x]∈A and [9x]∈A holds for any x. Prove that A is the set of all positive integers. ([x] denotes the integer part of x)
Solution
Since A is a nonempty subset of the positive integers, A has a minimum element m. If m>1 then m>3m≥[3m] and [3m]∈A. It is contrary to that m is the minimum element. So m=1.
Since 1∈A, 9k∈A. From this [381]=4∈A and 4⋅9=36∈A and [336]=3∈A. Then 3n∈A for n=1,2,… (*).
Lemma. There exists 3k type integer in the [n,3n] intervalum.
Proof of lemma. Let 3s≤n<3s+1. Then n<3s+1≤3n. □
Assume that there exists n such that n∈/A. Let us show that if a∈[n3p,(n+1)3p−1] then a∈/A. Suppose that a∈A, then [3a]∈A and [3a]∈[n3p−1,(n+1)3p−1−1]. Using this statement p times, we'll get [3…[3[3a]]=n∈A which is contradiction.
Since log3(n+1)−log3n>0 and limk→∞3k1=0, there exists a positive integer k such that log3(n+1)−log3n>3k1. From this 3klog3nn+1>1, then log3(nn+1)3k>log33 and (n+1)3k>3⋅n3k. Hence [n3k,3n3k]⊆[n3k,(n+1)3k−1]. By the lemma, there exists s∈N such that 3s∈[n3k,(n+1)3k−1] and 3s∈/A, contradicting (*). It means N⊆A.
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.