Олимпиадная задача Ященко: минимальная сумма монет для выражения 2009

Объясним, как эту задачу можно было бы решать. Заметим, что выражение можно составлять из произвольных чисел, заменив каждое из них на сумму соответствующего числа единиц. В частности,2009можно получить как сумму2009единиц. Но так как произведение обычно больше суммы, выгоднее числа не складывать, а умножать. Если разложить2009на простые множители, получится выражение7· 7· 41стоимостью7+7+41=55рублей. Теперь можно попробовать получить более дешёвым способом эти сомножители. Ясно, что если число стоит рядом с дешёвым, то и само оно не слишком дорогое. Например,41стоит рядом с числом40=5·2·2·2. Поэтому41можно получить за12рублей:5·2·2·2+1. Аналогично7=2·3+1. Воспользовавшись этим, можно получить2009за24рубля:(2·3+1)(2·3+1)(5·2·2·2+1). Можно попробовать удешевить один из сомножителей по-другому: например, представить41как42-1=2·3·7-1= 2·3 ·(2·3+ 1)-1. Снова получилось12рублей. Итак, дальше удешевлять отдельные сомножители так не получается, но можно попробовать применить ту же идею для каких-то их произведений. Например, можно представить7·7=49как48+1=2·2·2·2·3+1или50-1=5·5·2-1. К сожалению, это не позволяет улучшить результат (24рубля). Зато если представить7·41=287как288-1=2·2·222·3·3-1, то получится выражение для2009всего за23рубля:2009=(2·3+1)(2·2·2·2·2·3·3-1). Этот результат наилучший. Однако жюри неизвестно доказательство этого, не использующее компьютерного перебора. Комментарии.1. Докажем, что2009нельзя получить за20рублей, используя только операции сложения и умножения. Для этого докажем, что за20рублей нельзя получить больше, чем3⁶·2=1458<2009. Рассмотрим выражение ценой20рублей с наибольшим значением. Во-первых, ясно, что в этом выражении нет умножения на 1. Во-вторых, это выражение представляет собой произведение некоторых натуральных чисел. Действительно, фрагмент вида a+b· c можно заменить на(a+b)· c , сохранив цену, но увеличив значение выражения. В-третьих, каждый сомножитель меньше 5. Действительно,5+a можно заменить на2·3+a , сохранив цену, но увеличив значение выражения. Наконец, все четвёрки можно заменить на2·2. Значит, выражение является произведением нескольких двоек и троек с суммой20. Так как3·3>2·2·2(то есть три двойки выгодно заменить на две тройки), из таких выражений максимальное значение имеет3·3·3·3·3·3·2=1458. 2. У нас получилось, что оптимальный пример состоит из произведения двоек и троек. Это связно с тем, что2и3- ближайшие целые числа к постоянной Эйлера e=2,718...