Задача 67514
|
|
 |
Условие
В стране, валюта которой — тугрики, ходят только купюры двух целочисленных достоинств. И покупатель, и продавец имеют достаточно много и тех, и других купюр, но при каждом платеже могут использовать вместе не более $k$ купюр (включая сдачу). Известно, что так можно сделать платёж на любую целую сумму от 1 до $n$ тугриков. Каково наибольшее возможное $n$ (в зависимости от $k$)?Решение
Оценка. Пусть используются купюры достоинств $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)$.
