
4. Find the number of all 5-digit numbers (in base 10) each of which contains the block 15 and is divisible by 15 . (For example, 31545,34155 are two such numbers.)


Solution: Any such number should be both divisible by 5 and 3 . The last digit of a number divisible by 5 must be either 5 or 0 . Hence any such number falls into one of the following seven categories:
(i) $a b c 15$;
(ii) $a b 150$;
(iii) $a b 155$;
(iv) $a 15 b 0$;
(v) $a 15 b 5$; (vi) $15 a b 0$;
(vii) $15 a b 5$.

Here $a, b, c$ are digits. Let us count how many numbers of each category are there.

(i) In this case $a \neq 0$, and the 3 -digit number $a b c$ is divisible by 3 , and hence one of the numbers in the set $\{102,105, \ldots, 999\}$. This gives 300 numbers.

(ii) Again a number of the form $a b 150$ is divisible by 15 if and only if the 2-digit number $a b$ is divisible by 3 . Hence it must be from the set $\{12,15, \ldots, 99\}$. There are 30 such numbers.

(iii) As in (ii), here are again 30 numbers.

(iv) Similar to (ii); 30 numbers.

(v) Similar to (ii), 30 numbers.

(vi) We can begin the analysis of the number of the form $15 a b 0$ as in (ii). Here again $a b$ as a 2-digit number must be divisible by 3 , but $a=0$ is also permissible. Hence it must be from the set $\{00,03,06, \ldots, 99\}$. There are 34 such numbers.

(vii) Here again there are 33 numbers; $a b$ must be from the set $\{01,04,07, \ldots, 97\}$.

Adding all these we get $300+30+30+30+30+34+33=487$ numbers.

However this is not the correct figure as there is over counting. Let us see how much over counting is done by looking at the intersection of each pair of categories. A number in (i) obviously cannot lie in (ii), (iv) or (vi) as is evident from the last digit. There cannot be a common number in (i) and (iii) as any two such numbers differ in the 4 -th digit. If a number belongs to both (i) and (v), then such a number of the form $a 1515$. This is divisible by 3 only for $a=3,6,9$. Thus there are 3 common numbers in (i) and (ii). A number which is both in (i) and (vii) is of the form $15 c 15$ and divisibility by 3 gives $c=0,3,6,9$; thus we have 4 numbers common in (i) and (vii). That exhaust all possibilities with (i).

Now (ii) can have common numbers with only categories (iv) and (vi). There are no numbers common between (ii) and (vi) as evident from 3-rd digit. There is only one number common to (ii) and (vi), namely 15150 and this is divisible by 3 . There is nothing common to (iii) and (v) as can be seen from the 3 -rd digit. The only number common to (iii) and (vii) is 15155 and this is not divisible by 3 . It can easily be inferred that no number is common to (iv) and (vi) by looking at the 2-nd digit. Similarly no number is common to (v) and (vii). Thus there are $3+4+1=8$ numbers which are counted twice.

We conclude that the number of 5 -digit numbers which contain the block 15 and divisible by 15 is $487-8=479$.
