Экономный пример

Используя в качестве чисел любое количество монет достоинством 1, 2, 5 и 10 рублей, а также скобки и знаки четырех арифметических действий, составьте выражение со значением 2009, потратив как можно меньше денег.

И. Ященко

Решение. Решение этой задачи полезно начать с небольшого соревнования — попросите ваших учеников в течение 15 минут составить выражения и запишите на доске лучшие варианты. Может быть, кому-то удастся, используя те или иные разложения числа 2009 на множители, обойтись 25–27 рублями. (Можно просто представить число 2009 в виде суммы 2009 единиц, но это не экономно. Обычно, числа «выгоднее» складывать, а не умножать: сумма 1 + 1 + 1 обойдется в 3 рубля, а за произведение 1∙3 придется «заплатить» 4 рубля).
Например. Если разложить 2009 на простые множители, получится выражение 7∙7∙41 стоимостью 7 + 7 + 41 = 55 рублей (здесь 7 и 41 – суммы единиц). Как сделать сомножители «дешевле». Ясно, что если число стоит рядом с «дешевым», то и само оно не слишком «дорогое»: 41 стоит рядом с числом 40 = 5∙2∙2∙2 (которое «стоит» 11 рублей: 5 + 2 + 2 + 2), поэтому 41 можно получить за 12 рублей: 5∙2∙2∙2 + 1. Аналогично, 7 = 2∙3 + 1, что «стоит» 6 рублей. Воспользовавшись этим, можно получить 2009 за 6 + 6 + 12 = 24 рубля:
(2∙(2 + 1) + 1)(2∙(2 + 1) + 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∙2∙2∙2∙3∙3 – 1,
то получится выражение для 2009 всего за 23 рубля:
2009 = (2∙(2 + 1) + 1)(2∙2∙2∙2∙2∙(2 + 1)∙(2 + 1) – 1).
Компьютерным перебором можно проверить, что это действительно наилучший результат (это полезное упражнение по программированию).
К сожалению, нам неизвестно доказательство этого факта, не использующее компьютера. Мы будем рады получить такое доказательство от наших читателей.