Возьмём некоторое натуральное число. Переставим как-нибудь его цифры и прибавим новое число к исходному. Какой минимальный результат может получиться, если сделать несколько таких шагов?
Например, если начать с единицы, то наименьшим числом, которое можно получить за 10 шагов, будет число 466.
Всё вполне интуитивно: переставляем цифры в восходящем порядке, чтобы каждое сложение как можно меньше увеличивало результат. Однако если найти наименьшее число, которое можно получить за 11 шагов, им окажется не 932 = 466 + 466, а 896, находящееся в совершенно иной ветке:
Как видите, во второй ветви четырежды цифры сортировались не в строго возрастающем порядке, что позволило получить два числа с нулями. Эти нули, будучи выведенными вперёд в слагаемых, помогли сократить конечный результат.
А теперь вопрос. Какое наибольшее число шагов можно успеть сделать, пока число не станет пятизначным?
Например, если начать с единицы, то наименьшим числом, которое можно получить за 10 шагов, будет число 466.
Всё вполне интуитивно: переставляем цифры в восходящем порядке, чтобы каждое сложение как можно меньше увеличивало результат. Однако если найти наименьшее число, которое можно получить за 11 шагов, им окажется не 932 = 466 + 466, а 896, находящееся в совершенно иной ветке:
Как видите, во второй ветви четырежды цифры сортировались не в строго возрастающем порядке, что позволило получить два числа с нулями. Эти нули, будучи выведенными вперёд в слагаемых, помогли сократить конечный результат.
А теперь вопрос. Какое наибольшее число шагов можно успеть сделать, пока число не станет пятизначным?
Комментариев нет:
Отправить комментарий