** доске написано 88 различных натуральных чисел, больших 1000. Их сумма равна 999 999....

Question

На доске написано 88 различных натуральных чисел, больших 1000. Их сумма равна 999 999. Сережа прибавил к каждому числу число, образованное его тремя последними цифрами. (Например, из числа 1111 получилось бы 1222, из числа 1011 — число 1022, а из числа 10000 — оно само.) Все 88 результатов Сережа записал в тетрадь. Докажите, что в тетради записано хотя бы 45 различных чисел.

Answer 1

Найдем максимальное количество одинаковых чисел.

Рассмотрим любое число на доске. Для данной суммы числа с его последними тремя цифрами существует не более одной подобной суммы, но уже с другим числом. Иначе говоря, - имеет единственное решение для данных чисел a,b,c,d; Пусть это выполняется для чисел на доске. Теперь рассмотрим числа в тетради. Из вышесказанного следует, что эти 88 чисел можно разбить определенным образом на 44 пары, где в каждой паре будет два одинаковых числа. То есть может получиться 44 одинаковых числа. Но это с одной стороны. Рассмотрим другую сторону. Заметим, что сумма всех чисел нечетна - 999 999. Следовательно, в этой сумме есть хотя бы одно нечетное число. Взглянем на сумму числа с его тремя последними цифрами: ; Если число четное, то d - четно, значит результат делится на 4. Если d - нечетно, то результат не делится на 4. Раз существует хотя бы одно нечетное число, то рассмотрим одну из 44-ех пар, где четное и нечетное число. В самом начале мы сказали, что в 44 парах равные числа. Но из вышесказанного следует противоречие - сумма четного числа с его последними тремя цифрами не может равняться сумме некоего нечетного числа с его последними тремя цифрами, поскольку последнее не делится на 4, в отличие от четного. Это означает, что хотя бы одна пара будет содержать разные числа. То есть максимальное количество одинаковых чисел равно 44-1=43. А минимальное количество различных чисел равно 88-43 = 45. Значит всегда найдется по крайней мере 45 различных чисел.