Задача 35374

Тема:    [ Десятичная система счисления ]

Сложность: 4 Классы: 9,10,11

Условие

Дано натуральное число M. Докажите, что существует число, кратное M, сумма цифр которого (в десятичной записи) нечетна.

Подсказка

Удобно рассуждать от противного. Исследуйте, как меняется сумма цифр в суммировании двух чисел столбиком при переносе через разряд.

Решение

Допустим противное, пусть число M и все кратные числу M имеют четную сумму цифр. Если десятичная запись M оканчивается нулями, все их можно отбросить, отбросив столько же нулей и у всех кратных M. Это на сумму цифр не влияет. Итак, пусть M не оканчивается нулями. Рассмотрим сначала случай, когда предпоследняя цифра M - не девятка. Пусть запись числа M содержит n знаков. Можно найти число из n+1 цифры, делящееся на M, десятичная запись которого начинается с данной цифры b. В самом деле, среди 10ⁿ последовательных чисел b*10ⁿ, b*10ⁿ+1, ... , (b+1)*10ⁿ-1 найдется число, делящееся на M (поскольку M<10ⁿ). Итак, можно рассмотреть число S из n+1 цифры, начинающееся на цифру 9 и делящееся на M. Сложим числа S и M*10ⁿ. Поскольку число S начинается на 9, а число M не заканчивается на 0, при сложении чисел S и M*10ⁿ столбиком возникнет перенос в n-ом (считая слева) разряде. Перенос будет ровно в одном разряде, так как предпоследняя цифра M - не девятка. Следовательно, сумма цифр числа S+M*10ⁿ на 9 меньше, чем сумма цифр числа S, сложенная с суммой цифр числа M*10ⁿ. Таким образом, сумма цифр числа S+M*10ⁿ нечетна - противоречие. Рассмотрим теперь случай, когда предпоследняя цифра числа M - девятка. Тогда рассмотрим последовательность 3M, 9M, 27M ... (последовательные умножения на 3). Проследив, как при умножении на 3 меняются последние две цифры, нетрудно понять, что в этой последовательности найдется число, предпоследняя цифра которого - не девятка (при этом последняя цифра этого числа - не ноль). Для этого числа повторяем предыдущие рассуждения.

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

web-сайт

задача