The whole Mathematical Olympiad for Girls 2018 paper, one question at a time in order (5 questions). Press Mark as done after each one: your marks add up below.
One way to show that a number is not prime is to factorise it. A good way to do this in the particular cases in the question is to find values of \(a\) and \(b\) that allow us to express the numbers we are asked to show are not prime in the form \(a^2 - b^2\) or the form \(a^2 + 2ab + b^2\), which then allows us to use the factorisations of these expressions to find factors.
It may not initially be clear how to choose good values of \(a\) and \(b\). In part (a), we know that we want to add a square number, \(b^2\), onto the numbers that we are trying to factorise to get another square number, \(a^2\). Since the numbers in question both have six digits, it would be really nice if \(359999 + b^2\) and \(249919 + b^2\) were multiples of \(10000 = 100^2\). This motivates a choice of \(b = 1\) for 359999 and \(b = 9\) for 249919, giving \(359999 + 1^2 = 360000 = 600^2\) and \(249919 + 9^2 = 250000 = 500^2\).
A similar approach works for the second part.
(a)
\(a^2 - b^2 = (a - b)(a + b)\).
(i)
\(359999 = 360000 - 1 = 600^2 - 1^2 = 599 \times 601\), so 599 and 601 are factors of 359999, and so 359999 is not prime.
(ii)
\(249919 = 250000 - 81 = 500^2 - 9^2 = 491 \times 509\), so 491 and 509 are factors of 249919, and so 249919 is not prime.
(b)
\(a^2 + 2ab + b^2 = (a + b)^2\).
(i)
\(9006001 = 9000000 + 6000 + 1 = 3000^2 + 2 \times 3000 \times 1 + 1^2 = 3001^2\), so 3001 is a factor of 9006001, and so 9006001 is not prime.
(ii)
\(11449 = 10000 + 1400 + 49 = 100^2 + 2 \times 100 \times 7 + 7^2 = 107^2\), so 107 is a factor of 11449, and so 11449 is not prime.
Triangle \(ABC\) is isosceles, with \(AB = BC = 1\) and angle \(ABC\) equal to \(120^\circ\). A circle is tangent to the line \(AB\) at \(A\) and to the line \(BC\) at \(C\).
What is the radius of the circle?(10 marks)
[You should state clearly any geometrical facts or theorems you use in each step of your calculation. For example, if one of your steps calculates the size of an angle in a triangle you might justify that particular step with “because angles in a triangle add up to 180 degrees.”]
The first thing to do when faced with a geometry problem is to draw a large, labelled diagram, showing all the information given in the question. You should be careful not to assume any additional “facts” that are not explicitly given in the question, such as right angles or equal lengths that are not explicitly mentioned. If there are any further properties you need to use in your solution, you should explain why they follow from the given information.
When you try to draw the diagram for this question you will probably find that you need to extend the sides of the triangle past the points \(A\) and \(C\) to make it obvious that they are tangents to the circle.
Since the question asks for the radius of the circle, it seems useful to label the centre and connect it to the points on the circumference, as in the Diagram 2 above. You can now see how to use the fact that the lines \(AB\) and \(BC\) are tangents to the circle: The angle between a tangent and a radius is a right angle.
Another useful tip for solving geometry problems is to always bear in mind what you are given and what you are trying to find. Here you want to find the value of \(r\), which is the length of \(OA\), and you know the length \(AB{=}1\) and the angle \(OAB = 90^\circ\). This suggest that it might be useful to look at the right angled triangle \(OAB\). Notice that in this triangle, you also know that the angle at \(B\) is \(60^\circ\).
You can now complete the calculation using trigonometry. If you don’t remember the exact value of \(\tan(60^\circ)\) you can also use the fact that the triangle \(OAB\) is half of an equilateral triangle and then use Pythagoras.
Label the centre of the circle \(O\) and the radius of the circle \(r\). Then angle \(OAB = 90^\circ\), since a tangent to a circle is perpendicular to the radius at the point of contact. Also, by symmetry of the diagram, the line \(BO\) bisects the angle \(ABC\). Now consider triangle \(OAB\). It has a right angle at \(A\), angle \(ABO = 60^\circ\), \(AB = 1\) and \(OA = r\). Therefore \(\frac{r}{1} = \tan(60^\circ) = \sqrt{3}\) and so \(r = \sqrt{3}\).
Note
In the above solution, we stated that the line \(BO\) bisects the angle \(ABC\), ‘by symmetry’. This is an acceptable assertion in this case but, strictly speaking, you should prove it. This can be done by noting that triangles \(OAB\) and \(OCB\) have three equal sides and are therefore congruent.
Alternative
We can use the cosine rule in triangle \(ABC\), knowing \(\cos(120^\circ) = -\frac{1}{2}\), to find \(AC = \sqrt{3}\). Then note that angle \(AOC = 360 - 90 - 90 = 60^\circ\) (using the sum of the angles in the quadrilateral \(OABC\)), so triangle \(AOC\) is equilateral, and hence \(r = \sqrt{3}\).
Sheila the snail leaves a trail behind her as she moves along gridlines in Grid 1. She may only move in one direction along a gridline, indicated by arrows. Let \(b\),\(c\), \(d\) be the number of different trails Sheila could make while moving from \(A\) to \(B\),\(C\), \(D\) respectively.
Explain why \(b = c + d\).(2 marks)
(b)
Ghastly the ghost lives in a haunted mansion with 27 rooms arranged in a \(3 \times 3 \times 3\) cube. He may pass unhindered between adjacent rooms, moving through the walls or ceilings. He wants to move from the room in the bottom left corner of the building to the room farthest away in the top right corner, passing through as few rooms as possible. Unfortunately, a trap has been placed in the room at the centre of the house and he must avoid it at all costs.
How many distinct paths through the house can he take?(8 marks)
The key to both parts of this problem is to realise that, in order to get to \(B\), Sheila must get to either \(C\) or \(D\) first. From there, the only way she can go is to \(B\) (since she can only move in the direction of the arrows).
This means that any trail she can make while moving from \(A\) to \(B\) is either a trail from \(A\) to \(C\) or a trail from \(A\) to \(D\), with the final step to \(B\) added.
The same idea can be used in part (b), but now Ghastly moves between adjacent rooms instead of along grid lines. We can represent the mansion as three \(3 \times 3\) grids stacked on top of each other. Ghastly starts in the bottom front-left corner (marked \(S\) in the diagram) and wants to finish at the top back-right corner, marked \(F\).
The requirement of using the shortest possible route means that he only wants to move to the right, towards the back, or up (so never going back on himself).
Since the rooms are arranged in a cube, some rooms can be accessed from three adjacent rooms (from the left, front and below). For example, the final room can be accessed from the three rooms labelled \(A\), \(B\) and \(C\), so the total number of paths he can take is the sum of the number of paths leading to each of those three rooms.
Using this idea, it is now possible to fill in all 27 cells in the grid above, starting from the one marked \(S\), with numbers representing the number of paths which lead to that cell. The number in the cell labelled \(F\) will be the total number of distinct paths that Ghastly can take.
(a)
To get to \(B\), Sheila can either go to \(C\) and then move to the right, or go to \(D\) and then move up. Hence the number of trails she can make while moving from \(A\) to \(B\) equals the number of trails from \(A\) to \(C\) plus the number of trails from \(A\) to \(D\):\(b = c + d\), as required.
(b)
We can represent the rooms in the mansion by cells in three \(3 \times 3\) grids. Suppose that Ghastly wants to move from the room marked \(S\) to the room marked \(F\). In order to take the shortest possible path, he should only move to the right, towards the back, or up.
For each room, the number of ways he can get to that room equals the sum of the number of ways he can get to the rooms he could have visited immediately before it; those are the rooms to the left, in front, or below the current room (in some cases, not all three of those rooms exist).
We can therefore find the number of ways to get to each rooms by filling in the cells in the tables, starting from \(S\). There is only one way to get to the three rooms adjacent to \(S\) – that is, to come straight from \(S\). From there, we can fill in the tables as shown below. Note that Ghastly cannot go to the central room, so we place a 0 there.
From the table, the total number of ways to get to room \(F\) is \(18 + 18 + 18 = 54\).
Each of 100 houses in a row are to be painted white or yellow. The residents are quite particular and request that no three neighbouring houses are all the same colour.
(a)
Explain why no more than 67 houses can be painted yellow.(4 marks)
(b)
In how many different ways may the houses be painted if exactly 67 are painted yellow?
It is important to first set up some notation for a solution, it would be sensible to denote a house that is to be painted white by \(W\) and a house that is to be painted yellow by \(Y\).
For the first part of the problem if you try to come up with an example with as many houses painted yellow as possible you may end up with something like \(WYYWYY\dots WYYWYYW\), which contains exactly 66 yellow houses. When you try to improve on this you might come up with something like \(YWYYWY\dots YWYYWYY\) or perhaps \(YYWYYW\dots YYWYYWY\), both of which contain exactly 67 yellow houses. The subtlety comes in when you try to explain precisely why a 68th house cannot be painted yellow, no matter what colouring you choose. As no three neighbouring houses may be the same colour it makes sense to consider groupings of three houses at a time. To construct a proof it will be helpful to consider groupings which do not overlap. The simple groupings consisting of houses \((2, 3, 4), (5, 6, 7), \dots, (95, 96, 97), (98, 99, 100)\), which leave the first house on its own in a group of one, turn out to work well.
For the second part of the question the same groupings can be used to great effect. It is important that all allowable combinations of colourings for three houses are considered and writing these down is a good start. For a group of three houses, with one painted white and two painted yellow we have the colourings \(YYW\), \(YWY\) and \(WYY\). To work towards a solution we must consider how these colourings interact with one another. For example, can one colouring precede or follow another?
We shall denote a house that is to be painted white by \(W\) and a house that is to be painted yellow by \(Y\).
(a)
Let us number the houses 1 to 100 from left to right and consider the 34 blocks \((1), (2, 3, 4), (5, 6, 7), \dots, (95, 96, 97), (98, 99, 100)\). As no three neighbouring houses can all be the same colour there must be a maximum of two yellow houses in each of the 33 blocks of three houses. From this we can deduce that at most \(1 + 2 \times 33 = 67\) houses could be painted yellow.
Note
It is possible to paint exactly 67 houses yellow, one colouring that achieves this is \(Y\) followed by 33 blocks of \(WYY\).
(b)
Each block of three houses could be painted \(YYW\), \(YWY\) or \(WYY\). Note that the second colouring cannot be followed by the first and the third colouring cannot be followed by either the first or the second. This means that as soon as we choose the third colouring for one of our blocks of three houses then all successive blocks must have the same colouring. The first house must be painted \(Y\), as demonstrated in part (a), and the next block of three could be painted \(YWY\) or \(WYY\). The only choice we have is when we first paint a block \(WYY\), this could be in any of the 33 blocks of three houses or not at all. This means there are 34 different ways to paint the 100 houses, which adhere to the strict requests of the residents.
Sophie lays out 9 coins in a \(3 \times 3\) square grid, one in each cell, so that each coin is tail side up. A move consists of choosing a coin and turning over all coins which are adjacent to the chosen coin. For example if the centre coin is chosen then the four coins in cells above, below, left and right of it would be turned over.
(a)
Sophie records the number of times she has chosen each coin in a \(3 \times 3\) table. Explain how she can use this table to determine which way up every coin in the grid is at the end of a sequence of moves.(2 marks)
(b)
Is it possible that after a sequence of moves all coins are tail side down?(4 marks)
(c)
If instead Sophie lays out 16 coins in the cells of a \(4 \times 4\) grid, so that each coin is tail side up, is it possible that after a sequence of moves all coins are tail side down?(4 marks)
[In parts (b) and (c), if you think that it is possible, you should specify a sequence of moves, after which all coins are tail side down. If you think it is not possible, you should give a proof to show that it can’t be done, no matter which sequence of moves Sophie chooses to do.]
A good way to start thinking about this question is to try drawing several grids, and doing a few experiments to see what some sequences of moves will achieve. One good question to investigate is “does it matter which order the moves are done in?” Some early experimentation makes us suspicious that it doesn’t, and then we can start to think about the things that do affect the end position of each coin. Since we only care about which way up it is, we only care about how many times it has been turned over, and from there it is possible to deduce a process for reading the end position of the board off Sophie’s table.
For part (b), another observation is required: if we choose a coin twice, the end position of the board is the same as if we do not choose it at all, as turning over the coins in the cells adjacent to it twice returns them to their original state. So, what really matters is whether or not it is possible to have every coin turned over an odd number of times. Let each of the entries in the table below be the number of times that the coin in that cell has been chosen.\[\begin{array}{|c|c|c|}\hline a&b&c\\\hline d&e&f\\\hline g&h&i\\\hline\end{array}\]The question now amounts to whether or not we can choose whole numbers \(a, b, c, d, e, f, g, h, i\) such that the following sums are all odd:\[d{+}b, \quad b{+}f, \quad f{+}h, \quad h{+}d, \quad b{+}f{+}h{+}d, \quad a{+}e{+}c, \quad c{+}e{+}i, \quad i{+}e{+}g, \quad g{+}e{+}a\]where the first four sums are the number of times each of the four corner coins have been turned over, the fifth the coin in the centre, and the last four the coins on the sides. Some algebraic manipulation shows that it is not in fact possible to do this. A first step towards dealing with quite so many equations at once might be to spot that the first five expressions only concern \(b, d, f, h\) and that the last four only concern \(a, c, e, g, i\).
For part (c) an identical approach can be used, but now the set of sums produced can all simultaneously be odd. We just need to find a set of 16 numbers that satisfy this condition and then we can write down a sequence of moves that leaves the entire board tail side down.
(a)
The number of times that a particular coin \(C\) has been turned over is equal to the total number of times that a coin in a cell adjacent to \(C\) has chosen. So, to find the end position of \(C\), Sophie can add together all of the numbers in the table representing the cells adjacent to \(C\) to get \(C_{total}\) and turn \(C\) over \(C_{total}\) times. Doing this for each coin gives the end position of all of the coins in the grid.
(b)
It is not possible. Suppose that it can be done. Let \(a, b, c, d\) be the entries in Sophie’s table as shown in the table below. For a particular coin \(C\), if \(C_{total}\) is even, \(C\) will be tail side up, and if it is odd, \(C\) will be tail side down, since turning a coin over twice returns it to its original state. So, since the centre coin ends tail side down, we must have \(a + b + c + d\) odd. Since the coins in the top left and bottom right end up tail side down, we must have \(a + b\) and \(c + d\) odd. But then \((a + b) + (c + d)\) is a sum of two odd numbers, which is even. But we already know that \(a + b + c + d\) is odd, and it can’t be both odd and even, so the initial assumption that all of the coins can be tail side down after a series of moves must be wrong.\[\begin{array}{|c|c|c|}\hline \phantom{a}&a&\phantom{a}\\\hline b&&c\\\hline &d&\\\hline\end{array}\]
(c)
It is possible, for example in the following table, every coin is in a cell adjacent to exactly one other cell in which a coin has been chosen, so every coin is turned over exactly once; Sophie could choose each of the six coins in cells with a 1 once in any order.\[\begin{array}{|c|c|c|c|}\hline 0&1&1&0\\\hline 0&0&0&0\\\hline 1&0&0&1\\\hline 1&0&0&1\\\hline\end{array}\]
Alternative
In the following alternative solution to part (b) the term parity will be used, the parity of a number or variable refers to whether it is odd or even.
Let \(T\) be the number of coins in the main diagonal, running from top left to bottom right, which are tail side down. Initially \(T = 0\) and if all the coins are to be tail side down then \(T\) would take the value 3, which we will show is impossible.
Considering the square grid we can see that any move that changes the state of a single coin in the main diagonal will in fact change the state of exactly two coins in the main diagonal, it is impossible to change the state of 1 or 3 of these coins in a single move. If we consider two of the coins in the main diagonal which may be affected by a single move then there are three distinct cases, both coins may be tail side up, both may be tail side down or one tail side up and the other tail side down. In each of the three cases a single move would preserve the parity of the number of coins tail side down and hence preserve the parity of \(T\). We deduce that \(T = 3\) is not possible and hence it is impossible for all 9 coins to be tail side down.
Note
The above solution generalises to any square grid of size \((2n + 1) \times (2n + 1)\), where \(n\) is a positive integer.
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