Browse · MathNet
PrintFinal Round of National Olympiad
Estonia number theory
Problem
Let a finite decimal fraction be given. Juku starts appending digits to this fraction in such a way that each new digit equals the remainder of the sum of all digits existing so far in division by . (For instance, if the initial fraction is then the digits added to the end are , , etc.) Prove that the infinite decimal fraction obtained this way represents a rational number.
Solution
It suffices to show that the infinite decimal fraction is periodic. For that, note that each new digit except for the first digit is congruent to twice the previous digit modulo . Indeed, let be the existing at some time moment digits where is already added by Juku. Then the next digit satisfies Hence each new digit is uniquely determined by the last existing digit. As there are only a finite number of different digits, some digit must be added repeatedly. According to the fact just proven, all following digits are repeated as well.
Techniques
OtherRecurrence relationsPigeonhole principle