Задача 64851
|
|
 |
Условие
Назовём натуральное число ровным, если в его записи все цифры одинаковы (например: 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 ровных чисел по предположению индукции.
Замечания
8 баллов
