MOG 2018 Q5
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.
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)
Is it possible that after a sequence of moves all coins are tail side down?(4 marks)
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.]
Mathematical Olympiad for Girls 2018, Question 5. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: (b) No (c) Yes
Commentary
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.
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.
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}\]
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.
Solution © UK Mathematics Trust, from the MOG 2018 solutions.