Question

Число 302 представили в виде суммы нескольких натуральных чисел так, чтобы произведение этих слагаемых было наибольшим из возможных.
Сколько слагаемых в этой сумме?

Answer 1

1) Очевидно, среди слагаемых не должно быть единиц: если поменять два слагаемых a и 1 на сумму a + 1, произведение увеличится.

2) Пусть среди слагаемых a, не меньшее 5. Поменяем его на два слагаемых 2 и a - 2. Старый вклад в произведение был равен a, новый 2(a - 2), изменение 2(a - 2) - a = a - 4 > 0. Поэтому в произведении не может быть чисел, больших 4.

3) Четвёрки можно менять на две двойки и наоборот, произведение не меняется. Удобно считать, что четверок тоже среди слагаемых нет, если в ответе появтся две двойки, их можно будет переделать в четвёрки.

4) Если среди слагаемых есть три двойки, их можно поменять на две тройки, вклад в произведение увеличится: 2 * 2 * 2 < 3 * 3.

Итак, можно достичь максимального произведения, взяв некоторое количество троек и не больше двух двоек. Единственный вариант — взять 100 троек и одну двойку.

Ответ. 101.