Maths Olympiad Prep

Library / /5 of 6

Number theory Difficulty 5.9 AIME, harder Prove it Mongolia

Let AA be a nonempty subset of the positive integers. If xAx \in A, then [x3]A[\sqrt[3]{x}] \in A and [9x]A[9x] \in A holds for any xx. Prove that AA is the set of all positive integers. ([x][x] denotes the integer part of xx)

Solution

Since AA is a nonempty subset of the positive integers, AA has a minimum element mm. If m>1m > 1 then m>m3[m3]m > \sqrt[3]{m} \ge [\sqrt[3]{m}] and [m3]A[\sqrt[3]{m}] \in A. It is contrary to that mm is the minimum element. So m=1m = 1.

Since 1A1 \in A, 9kA9^k \in A. From this [813]=4A[\sqrt[3]{81}] = 4 \in A and 49=36A4 \cdot 9 = 36 \in A and [363]=3A[\sqrt[3]{36}] = 3 \in A. Then 3nA3^n \in A for n=1,2,n = 1, 2, \dots (*).

Lemma. There exists 3k3^k type integer in the [n,3n][n, 3n] intervalum.

Proof of lemma. Let 3sn<3s+13^s \le n < 3^{s+1}. Then n<3s+13nn < 3^{s+1} \le 3n. \square

Assume that there exists nn such that nAn \notin A. Let us show that if a[n3p,(n+1)3p1]a \in [n^{3^p}, (n+1)^{3^p} - 1] then aAa \notin A. Suppose that aAa \in A, then [a3]A[\sqrt[3]{a}] \in A and [a3][n3p1,(n+1)3p11][\sqrt[3]{a}] \in [n^{3^{p-1}}, (n+1)^{3^{p-1}} - 1]. Using this statement pp times, we'll get [[[a3]3]3=nA[\sqrt[3]{\dots[\sqrt[3]{[\sqrt[3]{a}]}]} = n \in A which is contradiction.

Since log3(n+1)log3n>0\log_3(n+1) - \log_3 n > 0 and limk13k=0\lim_{k \to \infty} \frac{1}{3^k} = 0, there exists a positive integer kk such that
log3(n+1)log3n>13k. \log_3(n+1) - \log_3 n > \frac{1}{3^k}.
From this 3klog3n+1n>13^k \log_3 \frac{n+1}{n} > 1, then log3(n+1n)3k>log33\log_3 \left(\frac{n+1}{n}\right)^{3^k} > \log_3 3 and (n+1)3k>3n3k(n+1)^{3^k} > 3 \cdot n^{3^k}. Hence [n3k,3n3k][n3k,(n+1)3k1][n^{3^k}, 3n^{3^k}] \subseteq [n^{3^k}, (n+1)^{3^k} - 1]. By the lemma, there exists sNs \in \mathbb{N} such that 3s[n3k,(n+1)3k1]3^s \in [n^{3^k}, (n+1)^{3^k} - 1] and 3sA3^s \notin A, contradicting (*). It means NA\mathbb{N} \subseteq 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.