Рассмотрим $%S=\{(x,y):23x+31y=1, x+y < 100\}\subset \mathbb Z^2$%

Найти $%(x,y)\in S$% для которого $%x+y$% наибольшее

Я нашел решение $%(x,y)=(31t-4,3-23t); x+y=8t-1$% и наибольшее значение $%95$% при $%t=12$%

Тут надо доказывать, что все решения имеют указанный выше вид? Даже если не надо, почему это так?

задан 6 Июл 6:05

Рассмотрите равенство по модулю 8

(6 Июл 10:52) spades

Общее решение линейных диофантовых уравнений описывается именно такой формулой. Чтобы её получить, достаточно найти подбором частное решение, и тогда общее будет иметь указанный вид. Это совсем элементарный факт. Подробности см. в учебниках типа Бухштаба.

Но здесь можно и по модулю 8 рассуждать, как предложил @spades. Тогда x+y=-1 mod 8, и x+y<=95, а равенство достигается. Но в общем случае таких соображений могло не хватить.

(6 Июл 11:16) falcao

Не понял, при чем тут модуль 8, что Вы хотите показать, рассматривая равенство по модулю 8?

Как получить формулу для решения мне понятно, но непонятно, как доказать, что эта формула покрывает все решения (хотя это вроде в задаче не требуется).

(6 Июл 20:28) Slater

@Slater: если a, b взаимно просты, то у уравнения ax+by=c есть частное решение (x0,y0). Пусть (x,y) -- произвольное решение. Тогда ax+by=ax0+by0 => a(x-x0)=b(y0-y). Левая часть делится на b. Ввиду взаимной простоты, x-x0 делится на b. Тогда x-x0=bt для некоторого целого t. Подставляя, имеем y0-y=at. Это даёт описание общего решения x=x0+bt, y=y0-at.

Это совсем элементарное рассуждение вообще-то надо знать, и я даже указал, где его нужно прочитать. Надо как можно скорее ликвидировать "зияющий" пробел в знаниях из элементарного курса теории чисел!

(7 Июл 1:03) falcao

Особенностью этой задачи является то, что 24 и 32 делятся на 8. На это обратил внимание @spades. Это даёт совсем простой способ решения: по модулю 8 мы имеем x+y=24x+32y-(23x+31y)=0-1=95, и ясно, что это наибольшее значение.

Будь на месте коэффициентов что-то произвольное, этот приём бы уже не сработал.

(7 Июл 1:05) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,711

задан
6 Июл 6:05

показан
61 раз

обновлен
7 Июл 1:05

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru