The final round of the South African Mathematics Olympiad will be taking place on Thursday, 28 July 2019. I have been writing about some of the problems from the senior paper from 2018. A list of all of the problems can be found here.
Today we will look at the fifth problem from the 2018 South African Mathematics Olympiad:
Determine all sequences of nonnegative integers such that , and divides for all .
Since the sequence is strictly increasing, we know that for all positive integers . (We could prove this rigorously by induction.) This means that for all , and so we know that is equal to either , or to for all positive integers . Perhaps we should try to figure out exactly when it is equal to , and when it is equal to . If we knew, for example, that we always have that , then we have reduced the problem to solving this recurrence relation.
So when is it possible that ? Looking at our derivation above, we see that is always strictly smaller than unless both and . i.e. We must have equality in each of the two inequalities that we used.
We see that if there is some positive integer such that , then we must have that , and so, since the sequence is strictly increasing, we have that for all . The sequence thus has some initial segment where , and then possibly switches to a sequence where . In fact, it is possible that this switch never occurs. We could have that for all positive integers . This is in fact a solution to the problem. We verify that if for all positive integers , then for all .
We now turn our attention to finding all of the possible sequences where either there is no positive integer such that , or where there is some positive integer such that , but for all .
Suppose that there are no positive integers such that . We then have that for all positive integers . This implies that
for all positive integers . We recall, or learn, that the sum of the first positive integers is , and so we find that
for all positive integers . To be more rigorous, we could prove this using the principle of mathematical induction. By construction, this satisfies for all , and so this is a valid solution to the problem for all values of .
Finally, what sequences arise if there is some positive integer such that , but for all ? Since and the sequence is strictly increasing, we have that for all positive integers . We thus have that for all , and so we find using a similar argument to before that
for all positive integers .
Thus we potentially have a solution where for some positive integer , we have that for , and for . The conditions of the problem are clearly satisfied for , since for these values of we have that , and by construction, we have that for all . Thus the only requirement that needs to be satisfied for this to be a valid solution is that divides . We thus require that divides . Since we have that , we must in fact have that . (We have that , and so the multiple of that is equal to must be itself.)
In summary, we found that all sequences that satisfy the conditions in the problem are given by
- for all positive integers ; or
- for all positive integers , where the value of can be chosen arbitrarily; or
- There is some positive integer such that for , and for all .