List of numbers | RMO 2015, Chennai Region Solutions

This is a problem from the Regional Mathematics Olympiad, RMO 2015 Chennai Region based on a List of numbers.

Problem: From the list of natural numbers 1, 2, 3, … suppose we remove all multiples of 7, all multiples of 11 and all multiples of 13.

1. At which position in the resulting list does the number 1002 appear?
2. What number occurs in the position 3600?

Discussion: 

(Part 1)

To find the position of 1002, we must delete all multiples of 7, all multiples of 11 and all multiples of 13 from 1 to 1002. We apply principle of inclusion and exclusion to find that:

$latex 1002 - { \left \lfloor \frac{1002}{7} \right \rfloor + \left \lfloor \frac{1002}{11} \right \rfloor + \left \lfloor \frac{1002}{13} \right \rfloor } + { \left \lfloor \frac{1002}{7 \times 11} \right \rfloor + \left \lfloor \frac{1002}{11 \times 13} \right \rfloor + \left \lfloor \frac{1002}{13 \times 7} \right \rfloor } - { \left \lfloor \frac{1002}{13 \times 11 \times 7} \right \rfloor } &s=2$

$latex = 1002 - (143+91+77) + (13+11+7) - 1 = 721 $

Hence the position of 1002 is 721 in the list.

(Part 2)

To find the number in the 3600 position, we assume that it is x. Then
$latex x - { \left \lfloor \frac{x}{7} \right \rfloor + \left \lfloor \frac{x}{11} \right \rfloor + \left \lfloor \frac{x}{13} \right \rfloor } + { \left \lfloor \frac{x}{7 \times 11} \right \rfloor + \left \lfloor \frac{x}{11 \times 13} \right \rfloor + \left \lfloor \frac{x}{13 \times 7} \right \rfloor } - { \left \lfloor \frac{x}{13 \times 11 \times 7} \right \rfloor } &s=2$
= ( 3600 )

Note that $latex 7\times 11\times 13 =1001 $ Hence from 1 to 1001 there are exactly 720 numbers (as found in Part 1) which are not divisible by 7, 11, 13. Similarly in the next 1001 numbers (from 1002 to 2002) we will have another 720 numbers which are not divisible by 7, 11, 13. To reach 3600 we have to do this exactly 5 times as $latex 720\times 5 = 3600 &s=2 $ . Hence there are $latex 3600 &s=2 $ numbers from 1 to $latex 1001 \times 5 = 5005 &s=2 $.

Thus the 3600th number is 5004.

Chatuspathi:

• Paper: RMO 2015 (Chennai)
• What is this topic: Combinatorics
• What are some of the associated concepts: Principle of Inclusion and Exclusion
• Where can learn these topics: Cheenta I.S.I. & C.M.I. course,Cheenta Math Olympiad Program, discuss these topics in the ‘Geometry’ module.
• Book Suggestions: Challenges and Thrills of Pre-College Mathematics by Venkatchala, Principles of Combinatorics