ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 64726
Темы:    [ Десятичная система счисления ]
[ Четность и нечетность ]
[ Примеры и контрпримеры. Конструкции ]
[ Доказательство от противного ]
Сложность: 4-
Классы: 10,11
В корзину
Прислать комментарий

Условие

Саша обнаружил, что на калькуляторе осталось ровно n исправных кнопок с цифрами. Оказалось, что любое натуральное число от 1 до 99999999 можно либо набрать, используя лишь исправные кнопки, либо получить как сумму двух натуральных чисел, каждое из которых можно набрать, используя лишь исправные кнопки. Каково наименьшее n, при котором это возможно?


Решение

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


Ответ

5.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Год 2014
Номер 77
класс
Класс 11
задача
Номер 4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .