4 Mathematical Olympiad for Girls questions from every year we have, newest year first. Use Difficulty › Position in the paper to practise the early (easier) or late (harder) questions, or the Year filter for one year.
Let \(p\) and \(q\) be different prime numbers, and let \(a = p^2\), \(b = pq\) and \(c = p^3q\). Which of \(ab\), \(bc\) and \(ca\) is a square number?(1 mark)
Halle would like to place nine of the ten integers \(1, 2, \ldots, 9, 10\) into the cells of a \(3 \times 3\) grid in such a way that the three numbers within each row are written in increasing order from left to right and the product of the three numbers within each row is equal to a square number.
(b)
Give an example showing that Halle’s task is possible.(4 marks)
(c)
How many different grids can Halle produce?(5 marks)
Answer: (a) \(bc\) (b) for example, rows \(2, 5, 10\);\(3, 6, 8\); \(1, 4, 9\) (c) \(12\)
Solution (UKMT)
Commentary
This question is about multiplying integers to make square numbers. The aim of part (a) is to get you thinking how prime factors combine to make squares. It hopefully leads you to realise that, in a square number, each prime factor must appear an even number of times. This should help you decide which nine of the ten numbers from 1 to 10 Halle should use, and also which can combine together to make squares.
This illustrates a very important result about prime numbers: If \(p\) and \(q\) are (different) prime numbers, and if \(p^mq^n\) is a square, then both \(p^m\) and \(q^n\) must be squares. Notice that this does not apply if \(p\) and/or \(q\) is not a prime; for example, \(6^3 \times 24^1 = 5184 = 72^2\), but neither \(6^3\) nor \(24^1\) are themselves squares. This is just one example of why prime numbers are so special and important in mathematics.
Part (b) asks you to find only one example. While looking for the example, you should make note of any choices you can make; this will help you count how many different grids Halle can produce in part (c).
You should remember that, although the numbers in each row need to be increasing, the rows themselves can we swapped round. So for each way of grouping the numbers into three groups of three, there are several different grids, because the rows can be swapped round. You can count how many different arrangements of the rows there are by thinking about how many options there are for the first row, how many for the second, and how many for the third.
With only three rows, you can also label them A, B and C and write out all possible arrangements. With more rows, the listing becomes difficult. You may know about the factorial function which counts the number of possible arrangements of \(n\) objects: \(n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1\) — can you explain why this is?
(a)
You can see that \(ab = p^3q\), \(bc = p^4q^2\) and \(ca = p^5q\). Of these, \(bc = (p^2q)^2\), so \(bc\) is the square number.
(b)
In a square number, each prime factor must appear an even number of times. So we need to find groups of three numbers so that, in each group, each prime factor appears an even number of times.
First we note that 7 only appears once in the ten numbers, so it can not be used. At this point, it is useful to write down the prime factorisations of the remaining nine numbers:\[1, 2, 3, 4 = 2^2, 5, 6 = 2 \times 3, 8 = 2^3, 9 = 3^2, 10 = 2 \times 5.\]Next, 5 only appears as a factor in 5 and 10, once in each, so those two must go together. Since \(5 \times 10 = 50 = 5^2 \times 2\), the third number in this group must have the factor of 2 appearing either once or three times. Any other prime factors would need to appear to an even power. Looking at the list above, the only numbers that can go with 5 and 10 are 2 or 8.
Suppose Halle chooses \(2, 5\) and \(10\) as the first group. Then 8 must go with 6 to make an even power of 2. But this group must also contain 3 to make an even power of 3. The final group is then \(1, 4\) and \(9\).
You should check that all three groups give square numbers: \(2 \times 5 \times 10 = 100\), \(3 \times 6 \times 8 = 144\) and \(1 \times 4 \times 9 = 36\).
(c)
When constructing the example in part (b), we had one choice to make: whether 2 or 8 went with 5 and 10. Choosing 2 gave us only one possible way to group the remaining numbers. If we choose 8 instead, then 2 must go with 6 and 3 must go with them as well, for the same reasons as given before. This gives another possible grouping: \(5 \times 8 \times 10 = 400\);\(2 \times 3 \times 6 = 36\);\(1 \times 4 \times 9 = 36\).
For each of the two possible groupings, the three rows can be arranged in \(3 \times 2 \times 1 = 6\) ways, so the total number of possible grids Halle can produce is \(6 \times 2 = 12\).
Freya creates a sequence with first term 1 and each subsequent term 5 more than the previous term. Hilary creates a different sequence with first term \(a\) and each subsequent term 3 less than the previous term. Both sequences are continued forever.
(a)
There is at least one number that appears in both sequences. Let \(c\) be the smallest of those numbers. Find the possible values of \(c\).(3 marks)
(b)
Given that there are exactly 100 numbers which appear in both sequences, find the possible values of \(a\).
The best way to approach a problem like this is to play around and see if you make any interesting observations. Freya’ sequence goes: \(1, 6, 11, 16, 21, \ldots\). Hilary’s sequence is decreasing, so it may be easiest to write it out “backwards” starting from a common term. For example, the smallest common term for the two sequences could be 1, in which case Hilary’s (backwards) sequence would go \(1, 4, 7, 10, 13, 16, 19, \ldots\). Can you see a pattern in the terms which overlap with Freya’s sequence? Can you prove your observation?
Could 6 be the smallest common term? What about 11, or 16, or 21? How is this related to the observation you made above?
For part (b), you may want to start by creating a sequence that has only two or three common terms with Freya’s (rather than 100). For example, if \(a = 16\) then Hilary’s sequence has exactly two terms in common with Freya’s (1 and 16). If \(a = 19\), there are still the same two common terms, and this is also the case if \(a = 22, 25\) or \(28\). However, if \(a = 31\) there are three common terms, \(1, 16, 31\). Can you see how to use similar reasoning to create a sequence which has exactly 100 terms in common with Freya’s? Do you have to start from 1 as the smallest common term?
(a)
Any common term must appear in Freya’s sequence. 1 can clearly appear in both sequences, in which case it is the smallest common term (as there are no terms smaller than 1 in Freya’s sequence). If 6 appears in Hilary’s sequence, then it continues \(3, 0, -3, \ldots\) and none of these overlap with Freya’s sequence. So 6 could be the smallest common term. Similarly, if 11 appears in Hilary’s sequence, then it continues \(8, 5, 2, -1, \ldots\) which again does not overlap with Freya’s, so the smallest common term could be 11. However, if 16 appears in Hilary’s sequence, then so does 1, so 16 cannot be the smallest common term.
In general, suppose \(x\) appears in both sequences. Then Freya’s sequence contains \(x - 5, x - 10, x - 15\) and Hilary’s sequence contains \(x - 3, x - 6, x - 9, x - 12, x - 15\). So \(x - 15\) also appears in both sequences. Moreover, there are no other terms between \(x\) and \(x - 15\) which appear in both sequences.
Therefore the smallest common term can be at most 15, and the possible values of \(c\) are \(1, 6\) and \(11\).
(b)
We have shown in part (a) that successive common terms differ by 15. Therefore the 100 common terms are \(c + 15k\), where \(k = 0, 1, \ldots, 99\) and \(c = 1, 6\) or \(11\).
When \(c = 1\), the 100th common term is \(1 + 15 \times 99 = 1486\), and this could be the first term of Hillary’s sequence. However, Hilary’s sequence could also start from \(1489, 1492, 1495\) or \(1498\) and the largest common term would still be 1486. But if Hilary’s sequence started from 1501, then this would be the 101st common term. So when \(c = 1\) there are five possible values of \(a\).
Similarly, when \(c = 6\), the first term of Hilary’s sequence could be \(6 + 15 \times 99 = 1491\), and also \(1494, 1497, 1500\) or \(1503\), but not 1506. Finally, when \(c = 11\), the first term of Hillary’s sequence could be \(1496, 1499, 1502, 1505\) or \(1508\).
Therefore, there are 15 possible values of \(a\), the smallest being 1486 and the largest 1508.
All the digits 1 to 9 are to be placed in the circles in Figure 1, one in each, so that the total of the numbers in any line of four circles is the same. In the example shown in Figure 2, the total is equal to 20.
Prove that if the total \(T\) is possible then the total \(40 - T\) is possible.
A sensible way to start is to try and create different totals. For example, try filling in the numbers so that the total on each line is 23; then try to make 17. This may lead you to spot a connection between the two configurations.
It is natural to ask which totals \(T\) are possible. That question can be answered (see the note after the solution), but it turns out that the answer is not needed to solve the actual problem.
The key is to look for a connection between a configuration with total \(T\) and one with total \(40 - T\). Since there are four numbers in each line, if each number \(d\) is replaced by \(10 - d\), the total of the four numbers in each line will change from \(T\) to \(40 - T\). It is important to check that this new configuration satisfies the conditions of the problem: that all the digits are different and each one is still between 1 and 9. (Even if this seems obvious, you should mention in your solution that you have checked it.)
Consider a numbering in which the total is \(T\). In each circle replace the number \(d\) with the number \(10 - d\). The digits 1 to 9 will still all be used once each, and now each line has total \(40 - T\).
Note
You can find which totals are possible by considering the sum of all nine numbers: \(1 + 2 + \dots + 9 = 45\). This should equal \(3T\) minus the sum of three corner numbers which are counted twice.
Denote the corner numbers \(a\), \(b\) and \(c\). Then\[3T - (a + b + c) = 45 \implies 3T = 45 + (a + b + c).\]Since \(a\), \(b\) and \(c\) are all different numbers between 1 and 9, the smallest and largest possible values of \(a + b + c\) are 6 and 24, respectively. This means that \(17 \le T \le 23\).
The question given an example with \(T = 20\). Try to construct examples with \(T = 17\) and \(T = 19\). You can then use the method described in the solution to find examples with \(T = 23\) and \(T = 21\).
To get \(T = 18\) we need \(a + b + c = 9 = 1 + 2 + 6 = 1 + 3 + 5 = 2 + 3 + 4\). For each of those options there are only a few possibilities to check, and none of them give a valid configuration. So \(T = 18\) is not possible. It follows that \(T = 22\) is not possible either.
In conclusion, the only possible totals are 17, 19, 20, 21 and 23.
The integer \(N\) is a square. Find, with proof, all possible remainders when \(N\) is divided by 16.
(b)
Find all positive integers \(m\) and \(n\) such that\[m! + 76 = n^2.\]
[The notation \(m!\) stands for the factorial of \(m\), that is, \(m! = m \times (m - 1) \times \dots \times 2 \times 1\). For example, \(4! = 4 \times 3 \times 2 \times 1\).]
Answer: (a) 0, 1, 4 and 9 (b) \((m, n) = (4, 10)\) and \((5, 14)\)
Solution (UKMT)
(a)
Commentary
It seems reasonable to start by working out remainders of some square numbers; you may soon notice a pattern. However, we need to produce a general argument.
If number \(n\) gives remainder \(r\) when divided by 16, we can write it as \(n = 16k + r\). The possible values of \(r\) are \(0, 1, 2, \dots, 15\). For example, if \(n\) gives remainder 5 when divided by 16 then \(n = 16k + 5\), so\[n^2 = (16k + 5)^2 = 256k^2 + 160k + 25.\]Notice that the first two terms are divisible by 16, so \(n^2\) gives the same remainder as 25 when divided by 16.
We can repeat this calculation for each \(r\) from 0 to 15 to get the list of all possible remainders. It is worth noticing a slight shortcut: the remainders seem to repeat from \(r = 8\). The solution below demonstrates why this is the case.
Write \(N = n^2\) and \(n = 8k + r\) where \(r\), the remainder when \(n\) is divided by 8, is one of 0, 1, 2, \(\dots\), 7. Then \(N = (8k + r)^2 = 64k^2 + 16kr + r^2\), and this leaves the same remainder as does \(r^2\) when divided by 16.
Those remainders \(R\) are shown in the following table.
r
R
0
0
1
1
2
4
3
9
4
0
5
9
6
4
7
1
Thus the possible remainders when \(N\) is divided by 16 are 0, 1, 4 and 9.
(b)
Commentary
Part (a) suggests that it may be helpful to look at remainders when dividing by 16. The possible remainders of \(n^2\) are 0, 1, 4 and 9, and 76 gives remainder 12. So \(m!\) needs to give the remainder 4, 5, 8 or 13 when divided by 16.
Looking at some factorial numbers suggests that after a certain point, they are all divisible by 16. This is because \(6!\) is a multiple of 16 and all further factorial numbers are multiples of \(6!\) (e.g., \(7! = 6! \times 7\), \(8! = 6! \times 7 \times 8\) and so on).
This means that \(m\) cannot be greater or equal to 6. We only need to check positive integers smaller than 6 to find all the solutions.
If \(m \ge 6\) then \(m!\) is a multiple of \(6! = 720\), which itself is a multiple of 16. Therefore the remainder when \(m! + 76\) is divided by 16 is the same as the remainder when 76 is divided by 16, which is 12. From part (a) we know, then, that \(m! + 76\) cannot be a square if \(m \ge 6\).
If \(m\) is 1, 2 or 3, then the remainders after division of \(m! + 76\) by 16 are 13, 14 and 2 respectively, and so \(m! + 76\) cannot be a square.
But if \(m = 4\) then \(m! + 76 = 24 + 76 = 100 = 10^2\), and if \(m = 5\) then \(m! + 76 = 120 + 76 = 196 = 14^2\). Therefore the only pairs \((m, n)\) of positive integers such that \(m! + 76 = n^2\) are \((4, 10)\) and \((5, 14)\).
Note
We could look at remainders on division by some other numbers. For example, a similar argument works if we look at division by 7. For \(m \ge 7\), \(m! + 76\) gives remainder 6 when divided by 7, and we can show that a square number cannot give this remainder.
We'd like to use Google Analytics cookies to count visits and see which pages help most. They're optional, and the site works exactly the same either way. Privacy policy