Задача о размене. Мах неразменная сумма

[eugrita]

Рассмотрим самый простой вариант задачи о размене -2 достоинства купюр
Обозначим $S$сумма, достоинства купюр $m_1,m_2$
считаем естественно $NOD(m_1,m_2)=1$
Надо найти максимальную неразменную сумму $Smax$
Компьютерные эксперименты показывают что она всегда существует и как правило небольшая
$m_1=5, m_2=7 S=33 $
$ m_1=5, m_2=9, S=31 $
$ m_1=7, m_2=11, S=59 $
$ m_1=7, m_2=13, S=71 $
и т.п. Возникает подозрение что можно указать ограничение на $Smax$
Возможно $Smax \le m_1 \cdot m_2$ или что-то вроде.
Может уже есть на эту тему математические результаты?

[Dmitriy40]

eugrita в сообщении #1381994 писал(а):

$m_1=5, m_2=7 S=33 $

Здесь видимо опечатка, должно быть
$m_1=5, m_2=7, S=\underline{2}3$

[Sender]

Рассмотрим вспомогательное диофантово уравнение $m_1u+m_2v=1$. Если $\text{НОД}(m_1,m_2)=1$, решение заведомо существует, причём можно показать, что найдётся решение $(u,v)$, удовлетворяющее соотношениям $\lvert u \rvert<m_2$, $\lvert v \rvert<m_1$. Очевидно, при положительных целых $m_1, m_2$ $u$ и $v$ не могут одновременно быть положительными. Если $u<0$, представим $S$ в виде $S=pm_1+q=pm_1+q(m_1u+m_2v)$, где $0<q<m_1$. Соответственно, у уравнения $m_1x+m_2y=S$ найдётся решение $(x,y)$, где $x=p+qu$, $y=qv$. Поскольку $q<m_1$, $\lvert u \rvert<m_2$, $x$ будет заведомо положительным при $p \geqslant m_1m_2$, т.е. при $S>m_1^2m_2$. В принципе, достаточно, чтобы было $S>\min(m_1^2m_2,m_1m_2^2)$. Оценка, конечно,не претендует на оптимальность.

[EUgeneUS]

Пока набивал, доказательство уже предоставили
Но пусть будет, там чуть другая и похоже несколько лучшая оценка.

(доказательство)

1. Соотношение Безу: если $m$ и $n$ - целые взаимно простые числа, то найдутся такие целые числа $x_0$, $y_0$, что $mx_0 + ny_0 =1$
2. Так как $m$ и $n$ положительные, то один из коэффициентов Безу положительный, а другой отрицательный, для определенности, путь $x_0 >0$, $y_0<0$

3. Тогда $mx_0 = n|y_0|+1$, это означает, что если в размене $|y_0|$ монет номиналом $n$, то мы можем всегда увеличить сумму на $1$, заменив их на $x_0$ монет номиналом $m$

4. Коэффициенты Безу определены неоднозначно: если найдены $x_0$, $y_0$, то остальные пары можно найти по формуле:

${(x_0 + kn, y_0 -km)| k \in \mathbb{Z}}$
5. Тогда можно подобрать такое $k$, чтобы коэффициенты при $m$ и $n$ поменяли знак. То есть найдутся такие коэффициенты, что $x_1 <0$, $y_1 > 0$
6. Тогда $ny_1 = m|x_1|+1$, это означает, что если в размене $|x_1|$ монет номиналом $m$, то мы можем всегда увеличить сумму на $1$, заменив их на $n$ монет номиналом $x_0$

7. Для любых сумм больше или равных $\tilde{S} = m|x_1| + n|y_0|$ в размене найти или $|y_0|$ номиналом $n$, или $|x_1|$ монет номиналом $m$, или и то и другое. То есть такие суммы можно увеличить . ЧТД

8. Воспользовавшись еще некоторыми свойствами коэффициентов Безу, $\tilde{S} = mn-1$
9. Оценку минимальной гарантированно разменной суммы можно ещё улучшить.

[Sender]

Так, кажется некто Сильвестр справился лучше. https://mathoverflow.net/questions/27884/non-negative-integer-solutions-of-a-single-linear-diophantine-equation

Vladimir Dotsenko писал(а):

every integer starting from $(a-1)(b-1)$ is representable as a non-negative combination

[mihaild]

Для любого целого $n$ существует единственная пара $(x, y)$ при $0 \leqslant x < m_2$, удовлетворяющая уравнению $x m_1 + y m_2 = n$ (без ограничений на $x$ существование решения следует из алгоритма Евклида, а добавлением / вычитанием $m_2$ из $x$ и $m_1$ из $y$ можно получить нужную оценку на $x$).
Если при этом $y > 0$, то размен возможен (и $x, y$ его реализуют), а если меньше нуля - то невозможен (нам нужно увеличить количество монет $m_2$, но тогда монет $m_1$ придется брать меньше нуля).
Получается что для $(m_2 - 1) m_1 - m_2 = m_1 m_2 - m_1 - m_2$ размен невозможен, а для всех больших - возможен.

[eugrita]

Dmitriy40 в сообщении #1382035 писал(а):

eugrita в сообщении #1381994 писал(а):

$m_1=5, m_2=7 S=33 $

Здесь видимо опечатка, должно быть
$m_1=5, m_2=7, S=\underline{2}3$

да - неправильно списал с программы

-- Пт мар 15, 2019 22:55:39 --

Sender в сообщении #1382068 писал(а):

Рассмотрим вспомогательное диофантово уравнение $m_1u+m_2v=1$. Если $\text{НОД}(m_1,m_2)=1$, решение заведомо существует, причём можно показать, что найдётся решение $(u,v)$, удовлетворяющее соотношениям $\lvert u \rvert<m_2$, $\lvert v \rvert<m_1$. Очевидно, при положительных целых $m_1, m_2$ $u$ и $v$ не могут одновременно быть положительными. Если $u<0$, представим $S$ в виде $S=pm_1+q=pm_1+q(m_1u+m_2v)$, где $0<q<m_1$. Соответственно, у уравнения $m_1x+m_2y=S$ найдётся решение $(x,y)$, где $x=p+qu$, $y=qv$. Поскольку $q<m_1$, $\lvert u \rvert<m_2$, $x$ будет заведомо положительным при $p \geqslant m_1m_2$, т.е. при $S>m_1^2m_2$. В принципе, достаточно, чтобы было $S>\min(m_1^2m_2,m_1m_2^2)$. Оценка, конечно,не претендует на оптимальность.

Что то не понял в формулах умножение или деление? Если умножение получим абсурд при $m_1=5,m_2=7$ имеем
$\min(m_1^2m_2,m_1m_2^2)=\min(25\cdot 7,5 \cdot 49)=175$.
когда в действительности 33

-- Пт мар 15, 2019 22:58:19 --

Лучший ответ EugeniUS

[EUgeneUS]

eugrita
У Sender оценка сверху. У меня - тоже.
У mihaild и по ссылке на некого сильвестра точные решения. Поэтому лучше у них.

[Sender]

(Оффтоп)

Про некоего это шутка была. На самом деле он довольно известен.Сильвестр, Джеймс Джозеф

[eugrita]

задача о размене достаточно важная в комбинаторике может решаться 2 основными способами 1)Методом производящих функций с перемножением соответствующих многочленов 2)рекурсивным методом (cм ЕГ информатика, рекурсивные вычисления).
Правда во 2 сл учитывается последовательность монет, т.е. для нахождения количества действительно разных способов надо делить на число сочетаний, например при $m_1=5,m_2=7,S=33$ рекурсией получим 5 а с учетом отсутствия перестановок надо поделить на 5 и будет 1
Не знаю, может возможно решение через формулу Пика.
Задача сводится к количеству целочисленных точек $B$на наклонном отрезке решетки
Для $k=2$ и прямоугольного треугольника ограниченного осями и линией $m_1 \cdot x+m_2 \cdot y=S$ она имеет вид $F=I+\frac{B}{2}-1$ площадь $F$ найти легко.
Т.е. задача размена сводится к оценке количества целочисленных точек $I$прямоугольного треугольника (неизвестно что легче)
Во 2 разновидности постановки задачи с учетом ограничений по количеству купюр каждого номинала видимо минимально гарантированной разменной суммы может и не существовать

[eugrita]

Хорошо спасибо. Шаря по литературе я как-то уловил но не понимаю связь теоремы Рамсея с этой задачей размена монет. Кто может ,объясните мне