Maths Olympiad Prep

Library / /7 of 13

Number theory Difficulty 5.5 AIME, harder Find the answer Italy

Problem:

Davide plays the following game: he starts from an integer between 1 and 99 and at each move replaces the number nn that he currently has with the number formed by the last two digits of 51n+5051 n+50 (or just by the last digit, if the second-to-last is 0). What is the maximum number of different numbers he can obtain in the course of the first 100 moves of a single game?

Pick one

Solution

Solution:

The answer is (A)\mathbf{( A )}. Suppose we start from an odd number nn: then we can write it as n=2k+1n=2k+1, and multiplying by 51 and adding 50 we find 102k+101=100k+100+(2k+1)102k+101=100k+100+(2k+1). Now 100k+100100k+100 is a number ending in two zeros, so the last two digits of 51n+5051n+50 are the same as those of nn, and the game stays fixed forever on nn.

If instead we start from an even number n=2kn=2k, the rule gives 102k+50102k+50, which ends with the same two digits as 2k+502k+50: so if 2k2k is less than 50 we simply find 2k+502k+50, and otherwise we find 2k502k-50 because of the carry. At the next step, the same reasoning tells us that 2k+502k+50 will become 2k+5050=2k2k+50-50=2k (since 2k+502k+50 is certainly at least equal to 50), and similarly 2k502k-50 will become 2k50+50=2k2k-50+50=2k: the game repeats every two turns, and therefore the different numbers we can obtain in the course of a game are at most 2.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.