2021 JMC 10 Problems/Problem 15

Problem

Let $a_0,a_1,a_2,\dots,a_{2021}$ be a sequence such that $a_0=1$ and $a_n = 10^n\cdot a_{n-1}+1$ for positive integers $n \ge1.$ How many terms of this sequence are divisible by $99?$

$\textbf{(A) } 0 \qquad\textbf{(B) } 20 \qquad\textbf{(C) } 21 \qquad\textbf{(D) } 91 \qquad\textbf{(E) } 112$

Solution

Note that $a_i$ has exactly $i+1$ ones and the rest are zeroes. By rules of divisibility by 9, the sum of the digits must be a multiple of 9, so we must have $9|(i+1)$ , which have $a_i$ divisible by 9.

For divisibility of $11$ , we claim that $11 |a_i$ if and only if $i$ is odd. Notice that $11$ , $1001$ , $100001, \dots$ are all divisible by $11$ by the sum of odd powers factorization of $1$ and $10$ . Because $a_i$ for odd $i$ are just linear combinations of these, they are multiples of $11$ . Because $1$ more than a multiple of a multiple of $11$ is not a multiple of $11$ , even $i$ fail on the basis of odd $i$ 's success. Combining, we must have $(n+1) \mid 18$ , and the answer is the number of $n= 1,2,\dots,2021$ that are congruent to $17 \pmod {18}$ . Thus, the answer is $\lfloor{\tfrac{2021-1}{18}}\rfloor = 112$ .

Page

Toolbox

Search

2021 JMC 10 Problems/Problem 15

Problem

Solution