Counting, Probability & Logic: HAM UKMT Intermediate Hamilton 2018 Q2

Hamilton 2018 Q2

HAMCurrent spec10 marksCounting, Probability & Logic Factors, Primes & Digits

2. How many nine-digit integers of the form ‘\(pqrpqrpqr\)’ are multiples of 24?
(Note that \(p\), \(q\) and \(r\) need not be different.)

Hamilton Olympiad 2018, Question 2. © UK Mathematics Trust. Original paper on ukmt.org.uk

Solution (UKMT)

Comment
When attempting to solve questions like this one, it is natural to turn to divisibility tests (which are often learned right at the start of secondary school). One key property of these tests is that they work in both directions: for example, all numbers which are divisible by 8 have their final three digits divisible by 8, and conversely all numbers with final three digits divisible by 8 are themselves divisible by 8. In the first solution below, this property is essential – without it we would not be able to guarantee that we have found all results.

Solution 1
In order to be a multiple of 24, any number must be both a multiple of 3 and a multiple of 8. Conversely, since 8 and 3 are coprime (i.e. they have no common factor greater than 1), any number which is a multiple of both 3 and 8 must be a multiple of 24. It is therefore sufficient for us to count all the numbers of the required form which are multiples of both 3 and 8.

The digit sum of ‘\(pqrpqrpqr\)’ is \(3(p + q + r)\), which is always a multiple of 3, so all numbers of the form ‘\(pqrpqrpqr\)’ are divisible by 3 (by the divisibility test for 3).

So now all we need to do is to count all the numbers of the required form which are multiples of 8, since they will also be a multiple of 3 and hence a multiple of 24.

By the divisibility test for 8, we need the three-digit number ‘\(pqr\)’ to be divisible by 8, and each three-digit multiple of 8 will give us a nine-digit number divisible by 8. So all that remains is to count the three-digit multiples of 8.

The smallest of these is 104 \((= 13 \times 8)\) and the largest is 992 \((= 124 \times 8)\), so there are 112 three-digit multiples of 8 and therefore 112 numbers of the form ‘\(pqrpqrpqr\)’ which are multiples of 24.

Solution 2
As in Solution 1, we can establish that we need ‘\(pqrpqrpqr\)’ to be a multiple of both 3 and 8.

Notice that ‘\(pqrpqrpqr\)’ \(= 1001001 \times pqr\). 1001001 is divisible by 3 so every number of the form is ‘\(pqrpqrpqr\)’ divisible by 3. Since 1001001 is odd, we need the three-digit number ‘\(pqr\)’ to be divisible by 8.

There are 124 multiples of 8 less than 1000; of these 12 are less than 100, so there are 112 three-digit multiples of 8 and hence 112 numbers with the properties given in the question.