количество сумм, возможных к выплате

[maxal]

Пусть имеется конечное количество номиналов (натуральные числа) и бесконечное количество банкнот каждого номинала как со стороны покупателя, так и кассира. Обозначим через $s_n$ количество различных сумм, которые покупатель может выплатить кассиру, если вместе они используют (для выплаты и сдачи) ровно $n$ банкнот. Докажите, что, начиная с некоторого члена, последовательность $s_1, s_2, s_3, \dots$ является арифметической прогрессией.

[Руст]

Если номиналы $0<m_1<m_2<...<m_k$, то x оплачиваемый n купюрами удовлетворяет неравенству $m_1n\le x\le m_kn$, т.е. $s_n$ растёт не быстрее линейной функции.
Представлению $\m_ix_i, \sum_i x_i=n$ сопоставим
$m_1n+\sum_{i=2}^k (m_i-m_1)x_i, x_i\ge 0$.
Пусть $(m_2-m_1)x_2+...+(m_k-m_1)x_k, x_i\ge 0$ не представляет a чисел. Тогда все числа кроме этих a и b чисел не представимых $(m_k-m_1)x_1+...+(m_k-m_{k-1})x_{k-1}$ из интервала $m_1n\le x\le m_n$ можно представить в виде суммы n купюр. Т.е. s_n=(m_k-m_1)n+1-a-b$ - арифметическая прогрессия.

[maxal]

Здесь не учтена возможность сдачи. Кроме того, не указано, с какого именно $n$ последовательность начинает вести себя как арифметическая прогрессия.

[Руст]

Тогда сводится к предыдущему с a=0 и $m_1=0$.