Задача 111904
|
|
 |
Условие
Используя в качестве чисел любое количество монет достоинством 1, 2, 5 и 10 рублей, а также (бесплатные) скобки и знаки четырех арифметических действий, составьте выражение со значением 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 рублей нельзя получить больше, чем 36·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 ...
