For each $1\leq i\leq 9$ and $T\in\mathbb N$, define $d_i(T)$ to be the total number of times the digit $i$ appears when all the multiples of $1829$ between $1$ and $T$ inclusive are written out in base $10$. Show that there are infinitely many $T\in\mathbb N$ such that there are precisely two distinct values among $d_1(T)$, $d_2(T)$, $\dots$, $d_9(T)$.
Problem
Source: ISL 2022 N5
Tags: number theory, IMO Shortlist, AZE IMO TST
09.07.2023 07:42
09.07.2023 17:39
I found a solution for this that finds a $T$ such that all values of $d_i(T)$ are equal. From this we find what the problem asks for. Let $n=1829$. We first define $d_{i,j}(T)$ to be the amount of times the digit $i$ appears in the multiples of $n$ until $T$, in the $j$-th position (from right to left). First, we note that $d_{i,j}(n(10^j+l))-d_{i,j}(nl)$ does not depend on the value of $i$, since the multiples of $n$ between $n(10^j+l)$ and $nl$ generate a complete residue system modulo $10^l$. Also, note that $d_{i,j}(0)=0$, and therefore, by taking $l=0,10^j,2\cdot10^j,\dots$, we must have that $d_{i,j}(nv10^j)$ does not depend on the value of $i$. See that this directly implies that $d_{i,j'}(nv10^j)$ does not depend on the value of $i$, for any $j'\leq j$. Now we take $T=10^k(10^m-1)$, where $k>\varphi(n)$ and $n\mid10^m-1$. We'll prove that $d_1(T)=d_2(T)=\dots=d_9(T)$. First, notice that $$d_i(T)=\sum_{1\leq j\leq m+k}d_{i,j}(T)=\sum_{1\leq j\leq k}d_{i,j}(T)+\sum_{k+1\leq j\leq m+k}d_{i,j}(T).$$See that the first summation does no depend on the value of $i$, since $10^k\mid T$. Now, for each multiple of $n$ with a certain digit $i$ in the $a$-th position, we can swap this digit with the digit in the $b$-th position when $\varphi(n)\mid a-b$ and keep the divisibility. Thus, we can make a bijection between the multiples of $n$ up until $T$ with $i$ in the $a$-th position, where $a>k$, with the multiples of $n$ until $T$ with $i$ in some position $b$, where $b<k$. Since we know that $d_{i,b}(T)$ does not depend on $i$, we conclude that $d_{i,a}(T)$ also does not depend on the value of $i$. This implies that any of the summations depend on the value of $i$, and thus our result is proven. To finish the problem, we just need to take $T-1$, since $d_9(T)$ will be smaller than the rest, and we're done. $\blacksquare$
09.07.2023 17:44
Also, why $1829$? Any number that satisfies $(10,n)=1$ would have done the trick. Why? Why? Why?
09.07.2023 18:19
It's the year that the famous Norwegian mathematician, Niels Henrik Abel died.
10.07.2023 10:48
MarkBcc168 wrote: Thus, for each $k$, the $k$-th digits have the same distribution as the unit digit. However, the sequence of unit digits is periodic with a period $10$, so there are exactly two possible values. This implies that the total distribution of all digits must have two possible values, done. What if those two values aren't distinct? It is easily fixable tho.
20.07.2023 13:17
Note that the digits of $1829N$ and $1829cN$ are the same for $c=\frac{10^n}{10^n-1}$, and $1829cN$ has the same distribution of digits in each position by cyclic symmetry since $1829cN$ and $1829cN10^k$ form the same residues modulo $10^n-1$. The units digit of $1829N$ have exactly two distinct frequencies, so there are exactly two distinct numbers in $d_i(T)$.
04.08.2023 20:26
Let $k$ be one of the infinitely many numbers such that $1829\mid 10^k-1$ and let $T=10^k-1$. We suppose that all numbers have leading zeroes so that there are exactly $k$ digits. Consider one number divisible by $1829$, and we will cyclically shift it: $\overline{a_1\dots a_{k}}$. Let this number be also written as $10a_0+a_k\equiv 0\pmod {1829}$, and we will show that $10^{k-1}a_k+a_0\equiv 0\pmod {1829}$. Indeed, note that \[10(10^{k-1}a_k+a_0)=10a_0+a_k+a_k(10^k-1)\equiv 0\pmod {1829}\]so our claim is true. If any number is divisible by $1829$, then so are all of its cyclic shifts. Therefore, if $f_1,f_2,\dots, f_9$ are the number of times digits $1,2,\dots,9$ appear as a units digit of some multiple of $1829$ with $k$ digits, then $d_i(T)=kf_1$, so it suffices to prove the same thing for $f_1,\dots,f_9$, which is trivial by $\pmod {10}$.
16.05.2024 02:05
Choose $10^k$ such that $1829|10^k-1$ then, $$1829|\overline{a_1a_2\dots a_k}\Rightarrow 1829|\overline{a_{k}a_1a_2\dots a_{k-1}}$$So the occurrence of each non-zero digit in a certain position has the same frequency as that digit in the units place. However the units digit cycles with period $10$ so we are finished.
02.08.2024 20:19
DottedCaculator wrote: Note that the digits of $1829N$ and $1829cN$ are the same for $c=\frac{10^n}{10^n-1}$, and $1829cN$ has the same distribution of digits in each position by cyclic symmetry since $1829cN$ and $1829cN10^k$ form the same residues modulo $10^n-1$. The units digit of $1829N$ have exactly two distinct frequencies, so there are exactly two distinct numbers in $d_i(T)$. If $c=\frac{10^n}{10^{n}-1}$ then $1829cN$ will not be a integer for many $N$ so how can this be a multiple of $1829?$
02.08.2024 20:22
MarkBcc168 wrote:
I didn't understand what you meant by these - "Thus, for each $k$, the $k$-th digits have the same distribution as the unit digit. However, the sequence of unit digits is periodic with a period $10$, so there are exactly two possible values. This implies that the total distribution of all digits must have two possible values, done" Question told all of the multiples from $1$ to $T$ so we have to consider $1829,3658,5487,...$ but it seems like all of the solutions just considers the multiples having $k$ digits such that $1829|10^{k} -1$ Please help me to understand
03.08.2024 00:37
For example, if $1829$ is replaced with $37$, then all multiple of $37$ up to $999$ is 037 074 111 148 185 222 259 296 333 370 407 444 481 518 555 592 629 666 703 740 777 814 851 888 925 962 999 Take one entry, say 148. Then, their cyclic rotations are 481 and 814; both are in the table. The cyclic rotation argument implies that the first, second, and third columns in this table have the same set of digits (in particular, all columns have 2 of $\{0,3,6\}$ and 3 of $\{1,2,4,5,7,8,9\}$). It then suffices to only consider the set of unit digits, which is periodic, so it has only two distinct numbers.
03.08.2024 14:38
MarkBcc168 wrote: For example, if $1829$ is replaced with $37$, then all multiple of $37$ up to $999$ is 037 074 111 148 185 222 259 296 333 370 407 444 481 518 555 592 629 666 703 740 777 814 851 888 925 962 999 Take one entry, say 148. Then, their cyclic rotations are 481 and 814; both are in the table. The cyclic rotation argument implies that the first, second, and third columns in this table have the same set of digits (in particular, all columns have 2 of $\{0,3,6\}$ and 3 of $\{1,2,4,5,7,8,9\}$). It then suffices to only consider the set of unit digits, which is periodic, so it has only two distinct numbers. But how did you get idea of it? The number was $1829$ it would impossible to try it like you tried with $37$ And why you got idea of trying $37$ instead of $1829$ How did you know their multiples before $T=10^t$ will be cyclic? It seems magical two me, How a people can find such an idea? :/ And how did you sure for $1829$ that there are exactly two distinct values for unit digits? What if there is exactly one distinct number like unit digits $74185296307418529630$