2006 SMT/Algebra Problems/Problem 1

Problem

A finite sequence of positive integers $m_i$ for $i=1, 2, \cdots, 2006$ are defined so that $m_1=1$ and $m_i=10m_{i-1}+1$ for $i>1$. How many of these integers are divisible by $37$?

Solution

Notice that $m_3=111=3\cdot37$. Also, if $m_{3n}$ is divisible by $37$, then $m_{3n+3}=10(10(10m_{3n}+1)+1)+1=10(100m_{3n}+11)+1=1000m_{3n}+111$ and $m_{3n+3}$ is also divisible by $37$. Therefore, all numbers of the form $m_{3n}$ are divisible by $37$.


Now, if we have a number of the form $m_{3n+1}$, this is equal to $10m_{3n}+1$ and is therefore $1$ more than a multiple of $37$. Similarly, $m_{3n+2}=100m_{3n}+11$ is $11$ more than a multiple of $37$. Thus, the only $m_i$ divisible by $37$ are those in which $i$ is a multiple of $3$.


The multiples of $3$ in $1, 2, \cdots, 2006$ are $3, 6, \cdots, 2004$, and dividing all of these by $3$ we get $1, 2, \cdots, 668$. Therefore, there are $\boxed{668}$ multiples of $37$.

See Also

2006 SMT/Algebra Problems