MOG 2020 Q4
Daniel and Alessia each have eight boxes labelled 1 to 8. To start, each of them has \(n\) balloons, all in their box 1.
Alessia is playing a game with her balloons. She may make the following move:
- Choose a box \(k\) containing at least two balloons. Pop a single balloon in box \(k\) and then move another balloon from box \(k\) to box \(k + 1\).
Find the value of \(n\) such that, after a finite number of moves, all that remains is a single balloon in box 8.(2 marks)
Daniel is playing a different game with his balloons. He may use any combination of the following two moves:
- Pop two balloons in box \(k\) and move a third balloon from box \(k\) to box \(k + 1\).
- Pop a single balloon in each of boxes \(k\) and \(k + 1\) and then move another balloon from box \(k + 1\) to box \(k + 2\).
What is the smallest value of \(n\) such that after a finite number of moves, all that remains
is a single balloon in box 4?
is a single balloon in box 8?(8 marks)
Mathematical Olympiad for Girls 2020, Question 4. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: (a) \(n = 128\) (b)(i) \(17\) (b)(ii) \(577\)
Commentary
It is a good idea to try some examples to develop your understanding of the rules. For example, with Alessia’s game, how many balloons do you need in box 1 in order to be able to get a balloon into box 2, or box 3? You may already be spotting a pattern, which you should try to explain. It may help to think “backwards”, starting with one balloon in box 8 and asking how many were needed in box 7, then box 6, and so on.
With Daniel’s game, the pattern is a bit harder to spot. You may quickly realise that it is more efficient to use the second move whenever you can, because it enables you to move a balloon two boxes forward. Can you write a more rigorous proof of this observation?
Thinking back from the final box is still a good idea. For example, to get a balloon in box 4 using the second move, you need two balloons in box 3 and another one in box 2. To get two balloons in box 3, you need four balloons in box 2 and another one in box 1. However, to get a balloon in box 2, you need to use the first move, which needs three balloons in box 1. You need to do one more step to complete the solution to part (b)(i).
If you want to use this method to work back from box 8, you need a systematic way to record the number of balloons needed at each “stage”. Try completing this table:\[\begin{array}{|c|c|c|c|c|c|c|c|}\hline 8&7&6&\quad 5\quad&4&3&2&1\\\hline 1&&&&&&&\\\hline &2&1&&&&&\\\hline &&4&2+2=4&1&&&\\\hline\end{array}\]An alternative method is to come up with a recurrence relation. This is an equation that tells you how many balloons you need to get into box \(m\) if you know how many balloons you need to get into previous boxes. For example, the recurrence relation for part (a) is \(a_m = 2a_{m-1}\): the number of balloons needed to get into box \(m\) is twice the number of balloons needed to get into box \(m - 1\). In part (b), if you are using the second move then the number of balloons required to get into box \(m\) will depend on the numbers required to get into both boxes \(m - 1\) and \(m - 2\). You just need to work out how many balloons are needed to get into boxes 1 and 2, and then you can use the recurrence relation to find the number required to any subsequent box. We will use this method in our first solution for part (b).
To get a balloon in a given box, Alessia needs two balloons in the previous box. Let \(b_m\) be the number of balloons required to get a single balloon into box \(m\). Then \(b_m = 2b_{m-1}\). Since \(b_1 = 1\) (we only need one balloon in box 1), \(b_8 = 2^7 = 128\).
Let \(a_m\) be the least number of balloons that Daniel needs to have in box 1 at the beginning, to allow him (eventually) to get a single balloon into box \(m\) —so the question is asking us to find the values of \(a_4\) and \(a_8\) , but it turns out to be useful to find the values of \(a_m\) for other small values of \(m\) too.
Clearly \(a_1 = 1\) and \(a_2 = 3\).
Now suppose \(m \ge 3\) : as getting a balloon into box \(m\) can’t be done without first getting a balloon into box \(m - 1\), we see that \(a_m \ge a_{m-1}\) (and \(a_{m-1} \ge a_{m-2}\) which we’ll use later).
Below we’ll find the key recurrence relation \(a_m = 2a_{m-1} + a_{m-2}\) (true for \(m \ge 3\)) and then use it to calculate the values of \(a_4\) and \(a_8\).
Each move Daniel makes consists of removing two balloons and moving a third. Equivalently we could think of this as removing three balloons and adding a new one, which we could call the ‘successor’ of each of these three balloons. Then at any fixed point in the future, each individual balloon which was in box 1 at the beginning will either still exist, or it will have been replaced by a successor, or it will have been replaced by a successor which will in turn have been replaced by its own successor, or \(\ldots\) (and so on). So each balloon at the start has ‘contributed’ towards exactly one balloon which exists at any particular point in the future – it can’t have contributed to more than one balloon existing at the same time.
To get a balloon into box \(m\) (where \(m \ge 3\)) we need three immediate ‘predecessor’ balloons – either three balloons in box \(m - 1\), or two balloons in box \(m - 1\) and one balloon in box \(m - 2\). Any balloon which existed at the beginning (in box 1) can only have contributed to at most one of these three balloons, by the previous paragraph.
This means that to get a balloon into box \(m\) there will need to be at least \(2a_{m-1}\) original balloons to allow two balloons to reach box \(m - 1\) and at least \(a_{m-1}\) or \(a_{m-2}\) different original balloons contributing to the other ‘predecessor’ balloon (which is in box \(m - 1\) or \(m - 2\)). But \(a_{m-1} \ge a_{m-2}\) and so we need a total of at least \(2a_{m-1} + a_{m-2}\) balloons at the start. And in fact, if you have \(2a_{m-1} + a_{m-2}\) balloons at the start, then you can get all three predecessor balloons and so you can get a single balloon into box \(m\).
So \(a_m = 2a_{m-1} + a_{m-2}\) which is the key result in this question, and is the recurrence relation which will help us to find the final answers; this recurrence gives that \(a_3 = 6 + 1 = 7\), and then \(a_4 = 14 + 3 = 17\), \(a_5 = 34 + 7 = 41\), \(a_6 = 82 + 17 = 99\), \(a_7 = 198 + 41 = 239\) and \(a_8 = 478 + 99 = 577\).
Hence Daniel needs at least 17 balloons to get a single balloon into box 4, and at least 577 balloons to get a single balloon into box 8.
Alternative
This is the solution for part (b)(ii). The answer for part (b)(ii) can be found by starting from box 4.
We can complete the table started in the commentary. To get one balloon in box 8, we need two balloons in box 7 and one balloon in box 6. This completes the first two lines of the table. To complete the third line, for each balloon in box \(m\) shown on the second line, we add two balloons to box \(m - 1\) and one balloon to box \(m - 2\). We continue this process, competing each line in turn, until we get to box 2. For each balloon in box 2, we need three balloons in box 1. The completed table is shown below.\[\begin{array}{|c|c|c|c|c|c|c|c|}\hline 8&7&6&5&4&3&2&1\\\hline 1&&&&&&&\\\hline &2&1&&&&&\\\hline &&4&2+2=4&1&&&\\\hline &&&8&4+8=12&4+2=6&1&\\\hline &&&&16&8+24=32&12+12=24&6+3=9\\\hline &&&&&32&16+64=80&32+72=104\\\hline &&&&&&64&32+240=272\\\hline &&&&&&&192\\\hline\end{array}\]The total number of balloons required is the sum of all the numbers in box 1:\[9 + 104 + 272 + 192 = 577.\]We have not explained why this strategy gives the smallest possible number of balloons; for example, could using the first move somewhere in the middle (and not just after getting to box 2) give a smaller total? To complete the argument, we need to explain why it is best to use the second move whenever possible, as was done at the start of the first solution.
Solution © UK Mathematics Trust, from the MOG 2020 solutions.