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$ .

Page

Toolbox

Search

2006 SMT/Algebra Problems/Problem 1

Problem

Solution

See Also