Maths Olympiad Prep

Library / /9 of 26

, 1994

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

You are given three lists AA, BB, and CC. List AA contains the numbers of the form 10k10^{k} in base 10, with kk any integer greater than or equal to 11. Lists BB and CC contain the same numbers translated into base 22 and 55 respectively:

AABBCC
10101020
1001100100400
1000111110100013000
\vdots\vdots\vdots

Prove that for every integer n>1n>1, there is exactly one number in exactly one of the lists BB or CC that has exactly nn digits.

Solution

Let bkb_{k} and ckc_{k} be the number of digits in the kkth term in lists BB and CC, respectively. Then
2bk110k<2bklog210k<bklog210k+1bk=klog210+1 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
ck=klog510+1. 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
1α+1β=1, \frac{1}{\alpha} + \frac{1}{\beta} = 1,
then the sequences kα\lfloor k \alpha \rfloor and kβ\lfloor k \beta \rfloor, k=1,2,k = 1, 2, \ldots, partition the positive integers.
Then, since
1log210+1log510=log102+log105=log10(25)=1, \frac{1}{\log_{2} 10} + \frac{1}{\log_{5} 10} = \log_{10} 2 + \log_{10} 5 = \log_{10}(2 \cdot 5) = 1,
the sequences bk1b_{k} - 1 and ck1c_{k} - 1 partition the positive integers, and therefore each integer greater than 11 appears in bkb_{k} or ckc_{k} exactly once. We are done.

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.