Назад
Задача

Назовём натуральное число ровным, если в его записи все цифры одинаковы (например: 4, 111, 999999).

Докажите, что любое n-значное число можно представить как сумму не более чем  n + 1  ровных чисел.

Решение

  Пусть  An = 1...1  (n единиц). Докажем по индукции более сильное утверждение:

      любое число  a ≤ An  можно представить как сумму не более чем n ровных чисел.

  База  (n = 1)  очевидна.

  Шаг индукции. Число An+1 само ровное. Если же  a ≤ An+1 – 1 = 10An,  то a можно записать в виде  qAn + r,  где  0 ≤ q ≤ 9,  0 ≤ r ≤ An.  Число qAn ровное, а r можно представить как сумму не более чем n ровных чисел по предположению индукции.

Ответ

Ответ задачи отсутствует

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет