We say that some positive integer $m$ covers the number $1998$, if $1,9,9,8$ appear in this order as digits of $m$. (For instance $1998$ is covered by $2\textbf{1}59\textbf{9}36\textbf{98}$ but not by $213326798$.) Let $k(n)$ be the number of positive integers that cover $1998$ and have exactly $n$ digits ($n\ge 5$), all different from $0$. What is the remainder of $k(n)$ on division by $8$?
Problem
Source: Baltic Way 1998
Tags: combinatorics proposed, combinatorics
hakN
28.04.2021 14:14
Answer: $\boxed{1}$ Let $a=\overline{a_1a_2\dots a_n}$. We will count them according to the first appearance of $1998$. Let $1\leq i < j < k < l\leq n$ such that $a_i = 1, a_j = 9 , a_k = 9 , a_l = 8$ and $a_m \neq 1 \ \forall m < i,$ $a_m \neq 9 \ \forall i < m < j,$ $a_m \neq 9 \ \forall j < m < k,$ $a_m \neq 8 \ \forall k < m < l.$ So there are $8^{i-1} \cdot 8^{j-i-1} \cdot 8^{k-j-1} \cdot 8^{l-k-1} \cdot 9^{n-l}$ such numbers. Also if $i=1, j=2 , k=3 , l=4$, we get a remainder $1$ and in the all other cases, we get remainder $0$, so our answer is $1$.
AmirMLK
20.03.2022 12:45
a(n) : the number of numbers with n digits that include1,9,9,8 with this order b(n) : ... that include 1,9,9 c(n) : ... that include 1,9 d(n) : ... that include 1 a(n)=b(n-1)+8*b(n-2)+...+(8^n-5)*b(4)+(8^n-4)*b(3) b(n)=c(n-1)+c*b(n-2)+...+(8^n-5)*c(4)+(8^n-3)*c(2) c(n)=d(n-1)+d*b(n-2)+...+(8^n-5)*d(4)+(8^n-2)*d(1) therefore , a(n) and b(n-1) and c(n-2) and d(n-3) have the same remainder on division by 8 fortunately , counting d(n) is very easy : 9^n - 8^n --> d(n) is always 1 (mod 8) so, a(n) is always 1 (mod 8)