Покупки, банкноты двух номиналов..

[arqady]

В одной из республик СНГ национальная валюта - шекель. Для удобства в этой республике используют при покупках только банкноты в $9$ и $11$ шекелей. Житель этой республики сделал покупок на $T$ шекелей. Найдите наибольшее $T$, при котором покупка в размере $T+1$ шекелей не могла бы быть осуществлена.
По моему, полный хаос в том же вопросе относительно банкнот в $p$ и $q$ шекелей, где $p$ и $q$ взаимно просты. Можно оценить, конечно, сверху $T(p,q)$...

[RIP]

Теорема. Пусть $p,q$ --- взаимно простые натуральные числа. Обозначим $A=\{px+qy\mid x,y\in\mathbb N_0\}$. Тогда $[pq-p-q+1;+\infty)\cap\mathbb Z\subset A$. Более того, если $n\in[0;pq-p-q]\cap\mathbb Z$, то

$$n\in A\qquad\Longleftrightarrow\qquad pq-p-q-n\notin A.$$

Соответственно, ответ: $T(p,q)=pq-p-q-1$ ($\min\{p,q\}\ge2$).

[maxal]

см.
topic14839.html
topic9137.html

[Ираклий]

Тема "Уравнение Диофанта первой степени" объединена с темой "Покупки".

Рассматривается уравнение $ax +by = n$, где $a$, $b$ и $n$ - натуральные числа, причем $a$ и $b$ взаимно просты. Вопрос: при каких $a$, $b$ и $n$ данное уравнение разрешимо в целых неотрицательных числах?

$n \geq a + b$ - очевидное необходимое условие разрешимости в натуральных числах.
$n \geq ab$ - можно показать, что это достаточное условие разрешимости в целых неотрицательных числах.

Но что творится на промежутке $[a+b; ab)$?

[mihiv]

При $n<ab$ уравнение имеет не более одного решения в натуральных числах.

[RIP]

Было неоднократно.

[Ираклий]

RIP
В той теме Вы даете ссылку на статью и формулируйте теорему. Теорема мне почти полностью ясна за исключением импликации справо налево. Почему если $\qquad pq-p-q-n\notin A$, то $n\in A$? Это как-то легко усмотреть? Или это нетривиально и нужно читать статью?

[RIP]

Это легко. Нужно представить $n$ в виде $n=pa+qb$, где $0\le a<q$ (скажем). Тогда $n$ принадлежит нашему множеству тогда и только тогда, когда $b\ge0$. Поскольку $pq-p-q-n=p(q-1-a)+q(-1-b)$, то всё и получается.

[Ираклий]

Спасибо! А есть ли еще какая-либо информация, кроме указанной симметрии, о распределении представимых чисел (т.е. чисел из $A$) на отрезке $[0, pq-p-q]$?

[RIP]

Не знаю.