APMO, 1994

Algebra Difficulty 7.6 National Olympiad, round 2 Prove it Asia Pacific Mathematics Olympiad (APMO)

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:

$A$	$B$	$C$
10	1010	20
100	1100100	400
1000	1111101000	13000
$\vdots$	$\vdots$	$\vdots$

Prove that for every integer

n>1

, there is exactly one number in exactly one of the lists

B

C

that has exactly

n

digits.

Solution

Let $b_{k}$ and $c_{k}$ be the number of digits in the $k$ th term in lists $B$ and $C$ , respectively. Then
$2^{b_{k}-1} \leq 10^{k} < 2^{b_{k}} \Longleftrightarrow \log_{2} 10^{k} < b_{k} \leq \log_{2} 10^{k} + 1 \Longleftrightarrow b_{k} = \left\lfloor k \cdot \log_{2} 10 \right\rfloor + 1$
and, similarly
$c_{k} = \left\lfloor k \cdot \log_{5} 10 \right\rfloor + 1.$
Beatty's theorem states that if $\alpha$ and $\beta$ are irrational positive numbers such that
$\frac{1}{\alpha} + \frac{1}{\beta} = 1,$
then the sequences $\lfloor k \alpha \rfloor$ and $\lfloor k \beta \rfloor$ , $k = 1, 2, \ldots$ , partition the positive integers.
Then, since
$\frac{1}{\log_{2} 10} + \frac{1}{\log_{5} 10} = \log_{10} 2 + \log_{10} 5 = \log_{10}(2 \cdot 5) = 1,$
the sequences $b_{k} - 1$ and $c_{k} - 1$ partition the positive integers, and therefore each integer greater than $1$ appears in $b_{k}$ or $c_{k}$ exactly once. We are done.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.