Платежи тугриками: задача по комбинаторике с ограничением купюр

Оценка.Пусть используются купюры достоинств $P$ и $Q$. Пусть купюр в платеже ровно $m$. Если сдача не нужна, то есть $m + 1$ вариант: от 0 до $m$ купюр $P$, остальные — $Q$. Если есть сдача, то платят купюрами одного вида, а сдачу дают купюрами другого вида. Тогда возможен $m - 1$ вариант: используется от 1 до $m-1$ купюр $P$, остальные — $Q$. Всего для $m$ купюр есть $2m$ вариантов. Суммируя по всем возможным $m$, получим $2(1 + 2 + \ldots + k) = k(k + 1)$ возможных вариантов сумм. Пример.Будем использовать купюры в $k$ и $k + 1$ тугрик. Докажем, что любая сумма от $1$ до $k(k+1)$ тугриков представляется в виде $ak + b(k + 1)$, где $|a| + |b| \leqslant k$. Сначала докажем, что все такие представления дают разные суммы. Пусть эта же сумма представлена иначе $ck + b(k + 1)$. Поскольку и тут $|c| + |d| \leqslant k$, то $|a| + |b| + |c| + |d| \leqslant 2k$. Из равенства $ak + b(k + 1) = ck + b(k + 1)$ следует, что $(a - c)k = (d - b)(k + 1)$. Тогда $a - c$ кратно $k + 1$, $d - b$ кратно $k$, и обе разности не равны 0. Значит, $k + 1 \leqslant |a - c| \leqslant |a| + |c|$, $k \leqslant |d - b| \leqslant |d| + |b|$, откуда $2k + 1 \leqslant |a| + |b| + |c| + |d|$. Противоречие. Итак, все представления указанного вида дают разные суммы. Так как максимальная сумма равна $k(k + 1)$, все суммы целые, и всего их $k(k + 1)$, то получаются все суммы от 1 до $k(k + 1)$.