Maths Olympiad Prep

Library / /14 of 30

, 2023

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

For each 1i91 \le i \le 9 and TNT \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 TNT \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 n10k1n \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=10k1T = 10^k - 1 or T=10k2T = 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(10k1):1i9}2\#\{d_i(10^k - 1) : 1 \le i \le 9\} \le 2. Indeed, if
#{di(10k1):1i9}=1 \#\{d_i(10^k - 1) : 1 \le i \le 9\} = 1
then, since 10k110^k - 1 which consists of all nines is a multiple of nn, we have
di(10k2)=di(10k1) for i{1,,8}, and d9(10k2)<d9(10k1). 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(10k2):1i9}=2\#\{d_i(10^k - 2) : 1 \le i \le 9\} = 2.

To prove that #{di(10k1)}2\#\{d_i(10^k - 1)\} \le 2 we need an observation. Now let
ak1ak2a0{1,,10k1} \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 ak1ak2a0\overline{a_{k-1}a_{k-2}\dots a_0} is divisible by nn if and only if ak2a0ak1\overline{a_{k-2}\dots a_0a_{k-1}} is divisible by nn. Indeed, this follows from the fact that
10ak1ak2a0ak2a0ak1=(10k1)ak1 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 10k110^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(10k1)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 10k1n\lfloor \frac{10^{k-1}}{n} \rfloor or 1+10k1n1 + \lfloor \frac{10^{k-1}}{n} \rfloor, we conclude that #{di(10k1)}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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.