Решение задачи 437
Условие:
У Оли Маринчак есть 1000 карточек с числами 1, 2, ..., 1000. Она разделила все карточки на две кучки, и в обеих кучках составила длинное число из всех карточек. Могут ли эти два числа совпасть?
Решение:
Посчитаем количество всех единиц. Забудем про число 1000 на время. Считаем, что оставшиеся числа состоят из трех цифр (дописываем ведущие нули если надо). Посчитаем, сколько раз единица встречается на первой позиции. Нетрудно видеть, что 100, потому что на второй и третьей позиции может стоять любая цифра от 0 до 9. Аналогично со второй и третьей позицией, значит всего единица встретится 300 раз среди трехзначных чисел. Вспоминаем про карточку с числом 1000, получается на всех карточках написано 301 единица.
Если бы Оле удалось получить два равных числа, то общее число единиц было бы четным, так как единицы встречаются в двух числах одинаковое количество раз. Но 301 нечетное число, значит такое невозможно.
Ответ: Нет.