Problem 4

Problem 4: Divisibility ( $✓$ ) 1999 Paper I

(i): How many integers greater than or equal to zero and less than 1000 are not divisible by 2 or 5? What is the average value of these integers?
(ii): How many integers greater than or equal to zero and less than 9261 are not divisible by 3 or 7? What is the average value of these integers?

Comments

There are a number of different ways of tackling this problem, but it should be clear that whatever way you choose for part (i) will also work for part (ii) (especially when you realise the signiﬁcance of the number 9261). A key idea for part (i) is to think in terms of blocks of 10 numbers, realising that all blocks of 10 are the same for the purposes of the problem.

Solution to problem 4

(i) Only integers ending in 1, 3, 7, or 9 are not divisible by 2 or 5. This is $4 ∕ 10$ of the possible integers, so the total number of such integers is $4 ∕ 10$ of 1,000, i.e. 400.

The integers can be added in pairs:

sum = (1 + 999) + (3 + 997) + \dots + (499 + 501) .

There are 200 such pairs, so the sum is $1, 000 \times 200$ and the average is 500.

A simpler argument to obtain the average would be to say that this is obvious by symmetry: there is nothing in the problem that favours an answer greater (or smaller) than 500.

Alternatively, we can ﬁnd the number of integers divisible by both 2 and 5 by adding the number divisible by 2 (i.e. 500) to the number divisible by 5 (i.e. 200), and subtracting the number divisible by both 2 and 5 (i.e. 100) since these have been counted twice. To ﬁnd the sum, we can sum those divisible by 2 (using the formula for a geometric progression), add the sum of those divisible by 5 and subtract the sum of those divisible by 10.

(ii) Either of the above methods will work. In the ﬁrst method you consider integers in blocks of 21 (essentially arithmetic to base 21): there are 12 integers in each such block that are not divisible by 3 or 7 (namely 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20) so the total number is $9261 \times 12 ∕ 21 = 5292$ . The average is $9261 ∕ 2$ as can be seen using the pairing argument $(1 + 9260) + (2 + 9259) + \dots$ or the symmetry argument.

Post-mortem

I was in year 7 at school when I had my ﬁrst encounter with lateral thinking in mathematics. The problem was to work out how many houses a postman delivers to in a street of houses numbered from 1 to 1000, given that he or she refuses to deliver to houses with the digit 9 in the number. It seemed impossible to do it systematically, until the idea of counting in base 9 occurred; and then it seemed brilliantly simple. I didn’t know I was counting in base 9; in those days, school mathematics was very traditional and base 9 would have been thought very advanced. All that was required was the idea of working out how many numbers can be made from nine digits (i.e. $9^{3}$ ) instead of from ten digits (i.e. $1 0^{3}$ ); and of course it doesn’t matter which nine.

Did you spot the signiﬁcance of the number 9261? It is $2 1^{3}$ , i.e. the number in base 10 that is written as 1000 in base 21. Note how carefully the question is written and laid out to suggest a connection between the two paragraphs (and also to highlight the difference). For the examination, the number 1,000,000 was used in part (i) instead of $1, 000$ in order to discourage candidates from spending the ﬁrst hour of the examination writing down the numbers from 1 to 1000.

Having realised that part (i) involves ${(2 \times 5)}^{3}$ and part (ii) involves ${(3 \times 7)}^{3}$ you are probably now wondering what the general result is, i.e:

How many integers greater than or equal to zero and less than ${(p q)}^{3}$ are not divisible by $p$ or $q$ ? What is the average value of these integers? Let’s make $p$ and $q$ co-prime, so that they have no common factors.

I leave this to you, with the hint that you need to think about only $p q$ , rather than ${(p q)}^{3}$ , to start with.