Let $A$ be the number of 2019-digit numbers, that is made of 2 different digits (For example $10\underbrace{1...1}_{2016}0$ is such number). Determine the highest power of 3 that divides $A$.
Problem
Source: X International Festival of Young Mathematicians Sozopol 2019, Theme for 10-12 grade
Tags: combinatorics, counting
25.09.2019 19:04
$A=A_0+A_1$, where $A_0$ is the number of 2019-digit numbers, that are made of the digit $0$ and the digit $k; 1\le k\le9$ and $A_1$ the number of 2019-digit numbers, that are made of 2 different non-zero digits. Calculus of $A_0$: A number containing only the digits $k$ and $0$ begins with $k$ and the next $2018$ digits can be any combination of $k$'s and $0$'s, except the configuration with $2018$ digits $k$. For a fixed $k$ exist $2^{2018}-1$ such numbers. Results for all $9$ possible $k$: $A_0=9(2^{2018}-1)$. Calculus of $A_1$: Let be $a,b\in\{1,2,\dots,9\}, a\ne b$. A number which begins with the digit $a$ can continue with any combination of $a$'s and $b$'s, except the configuration with $2018$ digits $a$. Similarly, a number which begins with the digit $b$ can continue with any combination of $a$'s and $b$'s, except the configuration with $2018$ digits $b$. Hence, exist $2(2^{2018}-1)$ numbers containing only the digits $a$ and $b$ ($2^{2018}-1$ numbers begin with $a$ and $2^{2018}-1$ numbers begin with $b$). With the elements of the set $\{1,2,\dots,9\}$ we can form $\binom{9}{2}=36$ distinct pairs $(a,b)$ (we consider $(a,b)$ and $(b,a)$ are not distinct). Results: $A_1=36\cdot2(2^{2018}-1)=72(2^{2018}-1)$. $A=A_0+A_1=81(2^{2018}-1)=3^4(2^{2018}-1)$. Results: $\nu_3{(A)}=4+\nu_3{(2^{2018}-1)}$. Calculating the powers of $2$ modulo $9$ results: $2^1\equiv 2\pmod{9}$; $2^2\equiv 4\pmod{9}$; $2^3\equiv 8\pmod{9}$; $2^4\equiv 7\pmod{9}$; $2^5\equiv 5\pmod{9}$; $2^6\equiv 1\pmod{9}$. $2018=6\cdot336+2\Longrightarrow 2^{2018}\equiv4\pmod{9}\Longrightarrow 2^{2018}-1\equiv3\pmod{9}\Longrightarrow$ $\Longrightarrow \nu_3{(2^{2018}-1)}=1$. Results: $\nu_3{(A)}=5$.