4
$\begingroup$

I stumbled on a very simple computer science question from the British Informatics Olympiad for schools and colleges. Embedded in it is a very interesting numbers theory problem. Here is the interesting part:

A digital river is a sequence of numbers where the number following n is n plus the sum of its digits. For example, 12345 is followed by 12360, since 1+2+3+4+5 = 15. If the first number of a digital river is k we will call it river k.

For example, river 480 is the sequence beginning {480, 492, 507, 519, ...} and river 483 is the sequence beginning {483, 498, 519, ...}.

Normal streams and rivers can meet, and the same is true for digital rivers. This happens when two digital rivers share some of the same values. For example: river 480 meets river 483 at 519, meets river 507 at 507, and never meets river 481.

Every digital river will eventually meet river 1, river 3 or river 9.

Source: http://www.olympiad.org.uk/papers/1999/bio/bio99r1q1.html

It is quite easy to show that rivers 1, 3 and 9 cannot meet. However, it appears to be more difficult to prove the remaining part:

How to prove that for any n > 0, river n eventually meets river 1, 3 or 9?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.