You are given three lists $A$, $B$, and $C$. List $A$ contains the numbers of the form $10^k$ in base $10$, with $k$ any integer greater than or equal to $1$. Lists $B$ and $C$ contain the same numbers translated into base $2$ and $5$ respectively: $$\begin{array}{lll} A & B & C \\ 10 & 1010 & 20 \\ 100 & 1100100 & 400 \\ 1000 & 1111101000 & 13000 \\ \vdots & \vdots & \vdots \end{array}$$ Prove that for every integer $n > 1$, there is exactly one number in exactly one of the lists $B$ or $C$ that has exactly $n$ digits.
Problem
Source: APMO 1994
Tags: floor function, logarithms, number theory unsolved, number theory
12.03.2006 06:48
Suppose that the i-th number in B has $a_i$ digits,and the i-th number in C has $b_i$ digits. So $2^{a_i-1}<10^i<2^{a_i},5^{b_i-1}<10^i<5^{b_i}$,and it's obvious that both of $\{a_i\},\{b_i\}$ is strictly increasing. If there exist $i,j\in\mathbb{N}$,$a_i=b_j$, Since $2^{a_i-1}<10^i<2^{a_i},5^{b_j-1}<10^j<5^{b_j}$ so $10^{a_i-1}<10^{i+j}<10^{a_i},a_i-1<i+j<a_i$ A contradiction.($a_i-1,i+j,a_i$ are integers). So there doesn't exist same number in $\{a_i\},\{b_i\}$ If there exists $k\in\mathbb{N},k>1$,$k\not\in\{a_n\}\cup\{b_n\}$. Since $b_1=2,b_2=3,a_1=4$,so $k\geq5$,there must exist $i,j\in\mathbb{N}$ such that $a_i<k<a_{i+1},b_j<k<b_{j+1}$. So $2^{a_i-1}<10^i<2^{a_i}\leq2^{k-1}<2^k\leq2^{a_{i+1}-1}<10^{i+1}<2^{a_{i+1}}$ $5^{b_j-1}<10^j<5^{b_j}\leq5^{k-1}<5^k\leq5^{b_{j+1}-1}<10^{j+1}<5^{b_{j+1}}$ So $10^{i+j}<10^{k-1}<10^k<10^{i+j+2}$ $i+j<k-1<k<i+j+2$ A contradiction. So for every integer $k$ , there is exactly one number in exactly one of the $\{a_i\},\{b_i\}$. So for every integer $k>1$, there is exactly one number in exactly one of the lists B or C that has exactly $k$ digits.
12.03.2013 15:12
Notice that the number of digits can be defined as: $B = \lfloor k\log_2(10)\rfloor$, and $C = \lfloor k\log_5(10) \rfloor$. Now, we evaluate $\dfrac{1}{\log_2(10)} + \dfrac{1}{\log_5(10)}$. $\Rightarrow \dfrac{\log_2(10) + \log_5(10)}{\log_2(10) \cdot \log_5(10)}$. Let $\log_2(10) = p, \log_5(10) = q \implies 2^{pq} = 10^{q}, 5^{pq} = 10^{p}$. Thus, $10^{pq} = 10^{p+q} \implies p + q = pq$ $\implies \dfrac{1}{\log_2(10)} + \dfrac{1}{\log_5(10)} = \dfrac{\log_2(10) + \log_5(10)}{\log_2(10) \cdot \log_5(10)} = 1$. Hence, by Beatty's theorem on that sequence, it follows every number length appears in that sequence, and the conclusion follows $\blacksquare$.
12.03.2013 19:31
Somewhat minor, but your computation could be simplified greatly: \[\frac{1}{\log_2{10}} + \frac{1}{\log_5{10}} = \log_{10}{2} + \log_{10}{5} = \log_{10}{10} = 1\]
08.03.2015 05:23
Beatty's Theorem.
13.12.2018 19:16
I did it in a much simpler manner: I defined the number of digits in $y$ (base $x$) as $\lfloor\log_x(y)\rfloor+1.$ Using that, it's easy to prove that the number of digits in $2^x$ plus the number of digits in $5^x$ is $x+1.$ Knowing that, I said that when we increment $x$ to be $x+1,$ exactly one of our two numbers is going to have one more digit than before. If it's $5^{x+1},$ then $5^x<10^a<5^{x+1},$ and otherwise, $2^x<10^b<2^{x+1},$ those being the other definition of number of digits (base $5$ or $2$), so either $10^a$ has $x+1$ digits base $5,$ or $10^b$ has $x+1$ digits base $2$, and one of them is always true, and only one can ever be true, so we have our proof.