Question

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

Answer 1

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

Рассмотрим любое число на доске. Для данной суммы числа с его последними тремя цифрами существует не более одной подобной суммы, но уже с другим числом. Иначе говоря, $1000a+100b+10c+d+[100b+10c+d]=1000m+100n+10k+l+[100n+10k+l], \;\; 0\leq b,c,d,n,k,l\leq 9, \;\;0$ - имеет единственное решение для данных чисел a,b,c,d; Пусть это выполняется для чисел на доске. Теперь рассмотрим числа в тетради. Из вышесказанного следует, что эти 88 чисел можно разбить определенным образом на 44 пары, где в каждой паре будет два одинаковых числа. То есть может получиться 44 одинаковых числа. Но это с одной стороны. Рассмотрим другую сторону. Заметим, что сумма всех чисел нечетна - 999 999. Следовательно, в этой сумме есть хотя бы одно нечетное число. Взглянем на сумму числа с его тремя последними цифрами: $1000a+100b+10c+d+100b+10c+d=1000a+200b+20c+2d$; Если число четное, то d - четно, значит результат делится на 4. Если d - нечетно, то результат не делится на 4. Раз существует хотя бы одно нечетное число, то рассмотрим одну из 44-ех пар, где четное и нечетное число. В самом начале мы сказали, что в 44 парах равные числа. Но из вышесказанного следует противоречие - сумма четного числа с его последними тремя цифрами не может равняться сумме некоего нечетного числа с его последними тремя цифрами, поскольку последнее не делится на 4, в отличие от четного. Это означает, что хотя бы одна пара будет содержать разные числа. То есть максимальное количество одинаковых чисел равно 44-1=43. А минимальное количество различных чисел равно 88-43 = 45. Значит всегда найдется по крайней мере 45 различных чисел.

Answer 2

Для доказательства этого утверждения, мы можем рассмотреть обратную ситуацию: предположим, что в тетради записано меньше 45 различных чисел после прибавления трех последних цифр. То есть, есть меньше 45 уникальных результатов Сережи.

Теперь давайте оценим минимально возможную сумму всех результатов после прибавления трех последних цифр. Минимальное число, которое Сережа мог прибавить к числу, чтобы получить новое уникальное число, равно 1. Поэтому сумма всех результатов Сережи составит не менее:

1 + 2 + 3 + ... + 45 = (45 * 46) / 2 = 1035

Теперь давайте оценим максимально возможную сумму всех результатов Сережи. Максимальное число, которое Сережа мог прибавить к числу, чтобы получить новое уникальное число, равно 999. Поскольку у нас 88 чисел, больших 1000, то максимальная сумма всех результатов Сережи составит не более:

999 * 88 = 87912

Таким образом, после прибавления трех последних цифр сумма всех результатов Сережи будет лежать в интервале от 1035 до 87912.

Но мы знаем, что исходная сумма чисел на доске составляет 999 999, и она не изменяется при прибавлении трех последних цифр. То есть, сумма всех результатов Сережи также составляет 999 999.

Из этого следует, что сумма всех результатов Сережи не может быть меньше 1035 и не может быть больше 87912, но она должна быть равна 999 999. Это означает, что в тетради записано хотя бы 45 различных чисел.

Таким образом, мы доказали, что в тетради записано хотя бы 45 различных чисел.