Задача
Саша обнаружил, что на калькуляторе осталось ровно n исправных кнопок с цифрами. Оказалось, что любое натуральное число от 1 до 99999999 можно либо набрать, используя лишь исправные кнопки, либо получить как сумму двух натуральных чисел, каждое из которых можно набрать, используя лишь исправные кнопки. Каково наименьшее n, при котором это возможно?
Решение
Покажем, что условия задачи выполнены, если исправными остались кнопки с цифрами 0, 1, 3, 4, 5. Действительно, любая цифра от 0 до 9 может быть представлена в виде суммы некоторых двух "рабочих" цифр. Пусть число от 1 до 99999999, которое мы хотим получить, состоит из цифр a1, a2, ..., a8 (некоторые из них, в том числе и первые, могут быть нулевыми). Представим каждую из них в виде суммы двух "рабочих" цифр: a1 = b1 + c1, a2 = b2 + c2, ..., a8 = b8 + c8. Тогда число, составленное из "рабочих" цифр b1, b2, ..., b8, и число, составленное из "рабочих" цифр c1, c2, ..., c8, дают в сумме желаемое число.
Предположим, что добиться желаемого можно для некоторого набора из четырёх "рабочих" цифр. Пусть a – какая-то нечётная цифра. Среди чисел от 1 до 99999999 найдется такое, которое заканчивается на a и содержит в своей десятичной записи "нерабочие" цифры. Тогда это число можно представить в виде суммы двух чисел, в записи которых содержатся только "рабочие" цифры. Поэтому для каждой нечётной цифры a найдутся такие две "рабочие" цифры (возможно, совпадающие), что их сумма оканчивается на a. С другой стороны, нетрудно видеть, что среди всех сумм пар четырёх "рабочих" цифр может быть не более четырёх нечётных чисел. Поэтому какая-то из цифр 1, 3, 5, 7, 9 не встречается в конце таких сумм. Противоречие.
Ответ
Чтобы оставлять комментарии, войдите или зарегистрируйтесь