Maths Olympiad Prep

Library / SAUDI ARABIAN IMO Booklet /12 of 25

SAUDI ARABIAN IMO Booklet, 2023

Number theory Difficulty 7.9 National Olympiad, round 2 Prove it Saudi Arabia

For each 1≤i≤91 \le i \le 9 and T∈NT \in \mathcal{N}, define di(T)d_i(T) to be the total number of times the digit ii appears when all the multiples of 20232023 between 11 and TT inclusive are written out in base 1010. Show that there are infinitely many T∈NT \in \mathcal{N} such that there are precisely two distinct values among d1(T),d2(T),…,d9(T)d_1(T), d_2(T), \dots, d_9(T).

Solution

Let n=2023n = 2023. First, we choose some kk such that n∣10k−1n \mid 10^k - 1. For instance, any multiple of φ(n)\varphi(n) would work since nn is coprime to 1010. We still show that either T=10k−1T = 10^k - 1 or T=10k−2T = 10^k - 2 has the desired property, which completes the proof since kk can be taken to be arbitrarily large.

For this it suffices to show that #{di(10k−1):1≤i≤9}≤2\#\{d_i(10^k - 1) : 1 \le i \le 9\} \le 2. Indeed, if
#{di(10k−1):1≤i≤9}=1 \#\{d_i(10^k - 1) : 1 \le i \le 9\} = 1
then, since 10k−110^k - 1 which consists of all nines is a multiple of nn, we have
di(10k−2)=di(10k−1) for i∈{1,…,8}, and d9(10k−2)<d9(10k−1). d_i(10^k - 2) = d_i(10^k - 1) \text{ for } i \in \{1, \dots, 8\}, \text{ and } d_9(10^k - 2) < d_9(10^k - 1).
This means that #{di(10k−2):1≤i≤9}=2\#\{d_i(10^k - 2) : 1 \le i \le 9\} = 2.

To prove that #{di(10k−1)}≤2\#\{d_i(10^k - 1)\} \le 2 we need an observation. Now let
ak−1ak−2…a0‾∈{1,…,10k−1} \overline{a_{k-1}a_{k-2}\dots a_0} \in \{1, \dots, 10^k - 1\}
be the decimal expansion of an arbitrary number, possibly with leading zeroes. Then ak−1ak−2…a0‾\overline{a_{k-1}a_{k-2}\dots a_0} is divisible by nn if and only if ak−2…a0ak−1‾\overline{a_{k-2}\dots a_0a_{k-1}} is divisible by nn. Indeed, this follows from the fact that
10⋅ak−1ak−2…a0‾−ak−2…a0ak−1‾=(10k−1)⋅ak−1 10 \cdot \overline{a_{k-1}a_{k-2}\dots a_0} - \overline{a_{k-2}\dots a_0a_{k-1}} = (10^k - 1) \cdot a_{k-1}
is divisible by nn. This observation shows that the set of multiples of nn between 11 and 10k−110^k - 1 is invariant under simultaneous cyclic permutation of digits when numbers are written with leading zeroes.

Hence, for each i∈{1,…,9}i \in \{1, \dots, 9\} the number di(10k−1)d_i(10^k - 1) is kk times larger than the number of kk-digit numbers which start from the digit ii and are divisible by nn. Since the latter number is either ⌊10k−1n⌋\lfloor \frac{10^{k-1}}{n} \rfloor or 1+⌊10k−1n⌋1 + \lfloor \frac{10^{k-1}}{n} \rfloor, we conclude that #{di(10k−1)}≤2\#\{d_i(10^k - 1)\} \le 2. This finishes the solution. □\square

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.