Solution. 9 Digits (#86)

Ответ: 9642 x 87531 = 843 973 902

Решение

Приведём элегантное решение с Glassdoor.

Лемма. Пусть есть два числа a и b. К одному из них справа приписывается цифра x. Произведение новых чисел будет наибольшим, если x приписывается к меньшему числу.

Действительно, пусть a > b, тогда
(10a + x)b < (10b + x)a, так как
10ab + xb < 10ab + xa, так как
xb < xa

Решение. Начнём с произведения двух цифр. Далее будем добавлять по одной цифре так, чтобы произведение новых чисел было наибольшим.

Как говорит лемма, надо приписывать следующую по величине цифру к меньшему числу, чтобы она умножала большее число.

9 8
9 87
96 87
…
9642 8753
9642 87531

Открытый вопрос. Почему максимизируя результат на каждом шаге, мы максимизируем итоговый результат?

Условие
Подсказка
Telegram