MOG 2019 Q5
Let \(n\) be a positive integer. Tracy writes a list of 10 whole numbers between 1 and \(n\) (inclusive). Each number in the list is either equal to, one less than, or one more than the number before it.
For example, when \(n = 7\):
Her list could be 5, 5, 6, 7, 6, 6, 5, 5, 6, 6 or 4, 4, 3, 2, 1, 1, 1, 1, 1, 1.
Her list could not be 1, 3, 3, 4, 5, 5, 6, 7, 7, 7 or 5, 6, 7, 8, 7, 6, 5, 5, 5, 5.
Suppose that \(n = 3\). Stacey forms a list by copying Tracy’s list, except that whenever Tracy writes a 1, Stacey writes a 3, and whenever Tracy writes a 3, Stacey writes a 1.
Which lists could Tracy write that would cause her list to be the same as Stacey’s?
Explain why Tracy can write as many lists that start 2, 2, 1 as start 2, 2, 3.
(3 marks)
For which \(n\) between 1 and 10 (inclusive) is the number of lists that Tracy could write odd?(7 marks)
Mathematical Olympiad for Girls 2019, Question 5. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: (b) \(n = 1\), 3, 5, 7 and 9
Commentary
There seems to be a lot going on in this question, so it is probably a good idea to start by writing out some lists. First make sure that you understand the rules. For \(n = 3\), can you write some of Tracy’s lists and the corresponding Stacey’s lists? What makes the lists the same? What makes them different?
Part (a)(ii) asks you to consider lists of two different types (those starting 2, 2, 1 and those starting 2, 2, 3) and to show that there is the same number of each type. A useful way of showing that two sets contain the same number of elements is to try and pair them up. Can you see how Stacey can help you? You may well find that thinking in terms of Tracy’s and Stacey’s lists is the easiest way to write an explanation.
In part (b), you will need to adapt Stacey’s rule slightly. Don’t forget to check and explain why Stacey’s new rule always generates a valid list (where each number is either equal to, one less or one more than the number before it). If the total number of Tracy’s lists is odd, what does that tell you about pairing them up with Stacey’s lists?
If Tracy writes a 3 at any point in her list, then Stacey will write a 1 at that point and so the lists will be different. Also, is Tracy writes a 1 at any point in her list, Stacey will write a 3 at that point and so the lists will be different. So, the only list that Tracy could possibly write that would cause Stacey to write the same list is the list where all ten entries are 2s. Indeed, this list does cause Stacey to have the same list as Tracy.
Note that whenever Tracy writes down a valid list of numbers, the list Stacey writes down is also a valid list of numbers. For any list \(L\) that Tracy can write, let \(S(L)\) be the list that this causes Stacey to write down.
Suppose Tracy writes a list \(L\) that starts 2,2,1. Then \(S(L)\) will start 2,2,3. We can get back to \(L\) from \(S(L)\) by replacing all of the 1s in \(S(L)\) with 3s and all of the 3s in \(S(L)\) with 1s. In symbols, this says:\[S(S(L)) = L.\]So we can pair up each list \(L\) that Tracy could write beginning 2,2,1 with the list \(S(L)\) beginning 2,2,3 that Stacey writes. Since this gives every list beginning 2,2,1 a unique partner beginning 2,2,3 (and vice versa), there must be the same number of lists beginning 2,2,1 as begin 2,2,3.
Suppose for each \(n\) that whenever Tracy writes a list, Stacey copies Tracy’s list except that whenever Tracy writes \(k\), Stacey writes \(n + 1 - k\). If Tracy writes a list \(L\), write \(S(L)\) again for the list that this causes Stacey to write.
Suppose Tracy writes a list which causes Stacey to write down the same list, i.e. \(L = S(L)\). If an entry in Tracy’s list is \(k\), then we must have \(k = n + 1 - k\), so \(k = \frac{n+1}{2}\). Therefore, if \(n\) is odd there is one list where Stacey and Tracey write down the same list, namely\[\frac{n+1}{2}, \frac{n+1}{2}, \frac{n+1}{2}, \frac{n+1}{2}, \frac{n+1}{2}, \frac{n+1}{2}, \frac{n+1}{2}, \frac{n+1}{2}, \frac{n+1}{2}, \frac{n+1}{2}.\]If \(n\) is even, then \(\frac{n+1}{2}\) is not a whole number so there are no lists that cause Stacey and Tracy to write down the same list.
Now, if Tracy writes the list \(L\) and this causes Stacey to write the list \(S(L)\), we can recover \(L\) from \(S(L)\) by replacing each entry of \(n + 1 - k\) with \(k\), for \(1 \le k \le n\). Since \(n + 1 - (n + 1 - k) = k\), this is the same as doing Stacey’s operation a second time, so\[S(S(L)) = L.\]So, all of the possible lists can be broken up into pairs of lists, where we pair the list \(L\) with its partner \(S(L)\). If no lists are paired with themselves, this splits all of the possible lists into pairs, so there must be an even number of possible lists. Therefore, in the case \(n\) is even, there is an even number of possible lists. In the case \(n\) is odd, there is one list \(M\) that is paired with itself. So, the number of possible lists except for \(M\) is even, and therefore the total number of possible lists including \(M\) is one more than an even number. So, the total number of possible lists is odd whenever \(n\) is odd.
The possible values of \(n\) for which Stacey can write an odd number of lists are 1, 3, 5, 7 and 9.
Solution © UK Mathematics Trust, from the MOG 2019 solutions.