2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Покупки
Сообщение01.01.2010, 00:55 
Аватара пользователя
Теорема. Пусть $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$).

 
 
 
 Re: Покупки
Сообщение01.01.2010, 02:33 
Аватара пользователя
см.
topic14839.html
topic9137.html

 
 
 
 Уравнение Диофанта первой степени
Сообщение22.03.2010, 14:48 
Аватара пользователя
Тема "Уравнение Диофанта первой степени" объединена с темой "Покупки".


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

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

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

 
 
 
 Re: Уравнение Диофанта первой степени
Сообщение22.03.2010, 17:34 
При $n<ab$ уравнение имеет не более одного решения в натуральных числах.

 
 
 
 Re: Уравнение Диофанта первой степени
Сообщение22.03.2010, 20:14 
Аватара пользователя
Было неоднократно.

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

 
 
 
 Re: Уравнение Диофанта первой степени
Сообщение23.03.2010, 13:29 
Аватара пользователя
Это легко. Нужно представить $n$ в виде $n=pa+qb$, где $0\le a<q$ (скажем). Тогда $n$ принадлежит нашему множеству тогда и только тогда, когда $b\ge0$. Поскольку $pq-p-q-n=p(q-1-a)+q(-1-b)$, то всё и получается.

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

 
 
 
 Re: Уравнение Диофанта первой степени
Сообщение25.03.2010, 20:04 
Аватара пользователя
Не знаю.

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group