Maths Olympiad Prep

Library / /167 of 264

Number theory Difficulty 6.1 National Olympiad Prove it Romania

Denote by p(a)p(a) the first digit of the natural number aa. Show that each of the sets
A={nNp(5n)p(2n)>0},B={nNp(5n)p(2n)<0} A = \{n \in \mathbb{N} \mid p(5^n) - p(2^n) > 0\}, \quad B = \{n \in \mathbb{N} \mid p(5^n) - p(2^n) < 0\}
has infinitely many elements.

Solution

For kNk \in \mathbb{N}^* there exists nkNn_k \in \mathbb{N}^* such that 2nk<10k<2nk+12^{n_k} < 10^k < 2^{n_k+1} (nk+1n_k + 1 is the smallest element of the set {mN10k<2m}\{m \in \mathbb{N}^* \mid 10^k < 2^m\}). As 2nk<10k<2nk+12^{n_k} < 10^k < 2^{n_k+1}, we get 10k<2nk+1<210k10^k < 2^{n_k+1} < 2 \cdot 10^k, so p(2nk+1)=1p(2^{n_k+1}) = 1.

Multiplying by 5nk+15^{n_k+1}, we have 10k5nk+1<10nk+1<210k5nk+110^k \cdot 5^{n_k+1} < 10^{n_k+1} < 2 \cdot 10^k \cdot 5^{n_k+1}. Dividing the first inequality by 10k10^k and the second by 210k2 \cdot 10^k, we get 510nkk<5nk+1<10nkk+15 \cdot 10^{n_k-k} < 5^{n_k+1} < 10^{n_k-k+1}, so p(5nk+1)5>p(2nk+1)p(5^{n_k+1}) \ge 5 > p(2^{n_k+1}).

From 2nk<10k<2nk+12^{n_k} < 10^k < 2^{n_k+1}, by dividing the second inequality by 22, we conclude 510k1<2nk<10k5 \cdot 10^{k-1} < 2^{n_k} < 10^k, so p(2nk)5p(2^{n_k}) \ge 5. Multiplying the first inequality by 5nk5^{n_k}, we obtain 10k15nk+1<10nk<10k5nk10^{k-1} \cdot 5^{n_k+1} < 10^{n_k} < 10^k \cdot 5^{n_k}, so by dividing the first one by 510k15 \cdot 10^{k-1} and the second by 10k10^k, we obtain 10nkk<5nk<210nkk10^{n_k-k} < 5^{n_k} < 2 \cdot 10^{n_k-k}, that is p(5nk)=1<p(2nk)p(5^{n_k}) = 1 < p(2^{n_k}).

The set {nkkN}\{n_k \mid k \in \mathbb{N}^*\} has an infinity of elements because nk>kn_k > k. As {nkkN}A\{n_k \mid k \in \mathbb{N}^*\} \subset A and {nk+1kN}B\{n_k + 1 \mid k \in \mathbb{N}^*\} \subset B, the sets AA and BB also have infinitely many elements.

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.