Областная олимпиада по математике, 2013 год, 11 класс

В шкатулке $n$ монет достоинством в натуральное число дукатов каждая на сумму $2n-1$ дукатов. Докажите, что любую сумму от 1 до $2n-1$ дукатов можно предоставить монетами из шкатулки.

Комментарий/решение

Рассмотрим базовую шкатулку : одна монета достоинством $n$,а остальные $n-1$ достоинством $1$ . Тогда условие выполнимо. Действительно , суммы от $1$ до $n-1$ получим суммами единиц, сумму в $n$ дукатов получим монетой $n$ , суммы от $n+1$ до $2n-1$ получим, суммируя $n$ с единичками . Изменим базовую шкатулку. Пусть монета с достоинством $n$ перейдет в монету $n-1$,а какая-то единичка станет двойкой. Ничего не изменится,условие вновь выполнимо. Меняя базовую шкатулку много ( но не бесконечно ) раз,получаем всевозможные шкатулки с суммой $2n-1$, в которых выполнимо условие.