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 .

The South African Mathematics Olympiad problems – MathemafricaJuly 23, 2019 at 2:51 pm[…] 2018 Olympiad problem 5 […]