JMC 2017 Q23
23. The positive integers from 1 to 150 inclusive are placed in a 10 by 15 grid so that each cell contains exactly one integer. Then the multiples of 3 are given a red mark, the multiples of 5 are given a blue mark, and the multiples of 7 are given a green mark.
How many cells have more than 1 mark?
- A 10
- B 12
- C 15
- D 18
- E 19
Junior Mathematical Challenge 2017, Question 23. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: E 19
As 3 and 5 are coprime, the squares that have more than one mark are multiples of both 3 and 5, (multiples of 15); or multiples of both 3 and 7, (multiples of 21); or multiples of 5 and 7, (multiples of 35); or multiples of 3, 5 and 7, (multiples of 105). However, the latter will be included in all of the first three categories. Between 1 and 150 inclusive, there are ten multiples of 15, seven multiples of 21 and four multiples of 35, making a total of 21 multiples. However, there is one multiple of 3, 5 and 7 between 1 and 150, namely 105. So 105 has been counted three times in those 21 multiples, but corresponds to exactly one marked square. Therefore the total number of marked squares is 21 − 2 = 19.
Solution © UK Mathematics Trust, from the JMC 2017 solutions. Longer versions with investigations: Solutions and investigations (PDF).