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

Проект МЦНМО
при участии
школы 57
Задача 116422
Темы:    [ Десятичная система счисления ]
[ Процессы и операции ]
[ Полуинварианты ]
Сложность: 4
Классы: 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.  Эту сумму можно получить при одной операции. Далее достаточно трижды заменить число на сумму его цифр.

Замечания

9 баллов

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

олимпиада
Название Московская математическая олимпиада
год
Номер 73
Год 2010
класс
Класс 9
задача
Номер 2010.9.6
олимпиада
Название Турнир городов
Турнир
Дата 2009/2010
Номер 31
вариант
Вариант весенний тур, основной вариант, 10-11 класс
Задача
Номер 7

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

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