Maths Olympiad Prep

Library / /24 of 152

Number theory Difficulty 5.4 AIME, harder Prove it Russia

Given are 111 distinct positive integers not exceeding 500. May it happen that for each of these numbers, its last digit coincides with the last digit of the sum of all other numbers?

Solution

Suppose this is possible. Denote the given numbers by a1,a2,,a111a_1, a_2, \dots, a_{111} and let their sum be SS. By the condition, for each index kk, the numbers aka_k and SakS - a_k have the same last digit. Hence, their difference S2akS - 2a_k is divisible by 1010. Therefore, for any kk, the number 2ak2a_k ends with the same digit as the sum SS. This means that the difference between any two numbers aka_k is divisible by 55. Thus, all 111111 distinct numbers aia_i must give the same remainder when divided by 55; but among the numbers from 11 to 500500, there are exactly 100100 numbers with any fixed remainder modulo 55. Contradiction.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.