BMO1 2020 Q1
Alice and Bob take it in turns to write numbers on a blackboard. Alice starts by writing an integer \(a\) between \(-100\) and 100 inclusive on the board. On each of Bob’s turns he writes twice the number Alice wrote last. On each of Alice’s subsequent turns she writes the number 45 less than the number Bob wrote last. At some point, the number \(a\) is written on the board for a second time. Find the possible values of \(a\).
British Mathematical Olympiad Round 1 2020, Question 1. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: \(a = 0, 30, 42, 45\)
Proposed by Daniel Griller
There are four possible starting numbers \(a\) which generate a repeat: 0, 30, 42 and 45.
We call the terms of the sequence written on the board \(a_1, a_2, a_3, \ldots\) where \(a_1 = a\). We will consider a more general version of the problem by writing \(s\) in place of 45. Now the sequence is determined by the rules \(a_{2n} = 2a_{2n-1}\) and \(a_{2n+1} = a_{2n} - s\) for \(n \ge 1\).
The sequence begins \(a, 2a, 2a - s, 4a - 2s, 4a - 3s, 8a - 6s, 8a - 7s, \ldots\).
In general we see that \(a_{2k} = 2^ka - (2^k - 2)s\) while \(a_{2k+1} = 2^ka - (2^k - 1)s\). These can be proved formally by induction, but this is obviously not required for the question.
We now have two cases to consider:
Case 1: \(a_{2k} = a\) for some \(k \ge 0\).
In this case \((2^k - 1)a = (2^k - 2)s\). The numbers \(2^k - 1\) and \(2^k - 2\) cannot share any factors great than one since any factor of both would divide their difference. Thus we must have \(2^k - 1\) is a factor of \(s\).
Turning to the specific problem at hand, we need \(2^k - 1\) to be a factor 45. The possible factors are \(1 = 2^1 - 1\), \(3 = 2^2 - 1\) and \(15 = 2^4 - 1\). These correspond to \(a = 0\), \(a = 30\) and \(a = 42\) respectively, all of which work.
Case 2: \(a_{2k+1} = a\) for some \(k \ge 1\).
In this case we have \((2^k - 1)a = (2^k - 1)s\) and, since \(k \neq 0\), this implies \(a = s = 45\) which also works.
Alternative
It is also fairly straightforward to solve the problem by trying values of \(a\) in turn.
If at any stage \(a_{2k} > 90\), then the subsequent odd and even numbered terms both form increasing sequences, so once their terms are larger than \(a\), the number \(a\) can never be repeated. Similarly if \(a_{2k} < 0\) at any stage, then the subsequent odd and even numbered terms both form decreasing sequences, so once their terms are less than \(a\), the number \(a\) can never be repeated.
Most values of \(a\) in the range \(-100\) to 100 give sequences which rapidly fall into the two categories above, meaning the four exceptional cases can be easily identified.
Solution © UK Mathematics Trust, from the BMO1 2020 solutions.
