Problem 6. Using any number of coins with denominations of $1, 2, 5$, and 10 rubles, as well as (free) parentheses and the four arithmetic operation signs, form an expression with a value of 2009, spending as little money as possible.

[28 rubles - 3 points; 26 rubles - 5 points;

24 rubles - 7 points; 23 rubles - 10 points] (I.V. Yashchenko)
Answer. The number 2009 can be obtained for 23 rubles in the following way: $2009=(2 \cdot(2+1)+1)(2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot(2+1) \cdot(2+1)-1)$.

Solution. Let's explain how this problem could be solved. Note that the expression can be formed from arbitrary numbers, replacing each with the sum of the corresponding number of ones. In particular, 2009 can be obtained as the sum of 2009 ones.

But since a product is usually greater than a sum, it is more cost-effective to multiply numbers rather than add them. If we factorize 2009 into prime factors, we get the expression $7 \cdot 7 \cdot 41$ with a cost of $7+7+41=55$ rubles.

Now we can try to obtain these factors more cheaply. Clearly, if a number is next to a cheap number, then the number itself is not too expensive. For example, 41 is next to the number $40=5 \cdot 2 \cdot 2 \cdot 2$. Therefore, 41 can be obtained for 12 rubles: $5 \cdot 2 \cdot 2 \cdot 2 + 1$. Similarly, $7=2 \cdot 3+1$. Using this, we can obtain 2009 for 24 rubles: $(2 \cdot 3+1)(2 \cdot 3+1)(5 \cdot 2 \cdot 2 \cdot 2+1)$.

We can try to make one of the factors cheaper in a different way: for example, represent 41 as $42-1=2 \cdot 3 \cdot 7-1=2 \cdot 3 \cdot(2 \cdot 3+1)-1$. Again, it costs 12 rubles.

Thus, it is no longer possible to further reduce the cost of individual factors, but we can try to apply the same idea to some of their products. For example, we can represent $7 \cdot 7=49$ as $48+1=2 \cdot 2 \cdot 2 \cdot 2 \cdot 3+1$ or $50-1=5 \cdot 5 \cdot 2-1$. Unfortunately, this does not improve the result (24 rubles). However, if we represent $7 \cdot 41=287$ as $288-1=2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3-1$, we get an expression for 2009 for only 23 rubles: $2009=(2 \cdot 3+1)(2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3-1)$.

This result is the best. However, the jury does not know a proof of this that does not use computer enumeration.

Comments. 1. Let's prove that 2009 cannot be obtained for 20 rubles using only addition and multiplication. For this, we will prove that for 20 rubles, it is impossible to obtain more than $3^{6} \cdot 2=1458 \cdot 2 \cdot 2$ (that is, three twos are more cost-effective to replace with two threes), among such expressions, the maximum value is $3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 \cdot 2=1458$.