Олимпиадная задача по математике: инварианты, системы счисления, 10-11 класс
Дано натуральное число. Разрешается расставить между цифрами числа плюсы произвольным образом и вычислить сумму (например, из числа 123456789 можно получить 12345 + 6 + 789 = 13140). С полученным числом снова разрешается выполнить подобную операцию, и так далее. Докажите, что из любого числа можно получить однозначное, выполнив не более 10 таких операций.
Разобрать решение
Хватит четырёх операций. Для чисел, меньших 1000, это очевидно. Иначе разобьём число на четырёхзначные куски (не начинающиеся с нуля) плюс, возможно, нули, плюс, возможно, одно меньшее число в конце (например, 12300004500060 = 1230 + 0 + 0 + 0 + 4500 + 0 + 60). Если получилось k четырёхзначных кусков, то сумма не меньше 1000k. Будем теперь по одному заменять ненулевые слагаемые на сумму их цифр. В конце она будет не больше 36k + 27 < 100k. Значит, количество разрядов в сумме уменьшится. Но так как на каждом шаге сумма уменьшалась меньше чем на 9999, то последняя сумма перед уменьшением количества разрядов выглядела так: 10....0abcd. Эту сумму можно получить при одной операции. Далее достаточно трижды заменить число на сумму его цифр.
Обсуждение
0Комментариев пока нет.