Линейные диофантовые уравнения (стр. 3 из 4)

Ответ: 5 стаканов.

Практически дословное повторение рассуждений, проведенных при решении задач 3 и 4, позволяет доказать, что общее решение уравнения ах + bу = с представляет собой сумму частного решения (х₀ ; у₀) этого уравнения и общего решения соответствующего однородного уравнения ах + by= 0. Отсюда, в свою очередь, вытекает следующая важная общая теорема.

Теорема 5. Если числа а и b— взаимно простые, то уравнение ах + by= с имеет бесконечно много решений в целых числах, которые находятся во взаимно однозначном соответствии с множеством целых чисел Z(то есть могут быть занумерованы целыми числами) и описываются формулой: х_n= х₀ + bn_,y_n = y₀- an, где n

Z — «номер» решения, а х₀, у₀ — частное решение (которое существует в силу теоремы 3).

Важно подчеркнуть, что в рассмотренном методе решения уравнений вида ах + by = с частное решение мы ищем только для того, чтобы свести дело к однородному уравнению. Иногда, как, например, в следующей задаче, этого можно добиться и проще.

Задача 5. Найти все наборы натуральных чисел х_, у, z, удовлетворяющие следующим условиям:

Решение. Исключим г из второго уравнения системы: г = у + 7. Тогда первое уравнение примет вид:

11х - 6у = y + 7

11x – 7y = 7

Если перенести свободный член 7 из правой части и сгруппировать члены 7у и 7, то мы получим уравнение

11x-7(y + 1) = 0,

которое является однородным относительно хи«^ву+ 1. В силу теоремы 1 его общее решение в целых числах имеет вид: х = 7n, у + 1 = 11n, где n— произвольное целое число. Соответственно, (x; у) = (7n; 11n -1), n

Z. Чтобы x и у были натуральными, должны быть выполнены условия 7n > 0 и 11n -1 > 0, что равносильно тому, что n— натуральное число. Если у — натуральное число, то z= y+ 7 автоматически будет натуральным.

Итак, общее решение системы из двух первых уравнений в натуральных числах имеет вид: (х; у; z) = (7n; 11n - 1; 11n + 6), где n — произвольное натуральное число.

Дополнительное условие, что х ≤ 20, означает, что параметр n < 2. Итак, для nесть всего два возможных значения: 1 и 2. Им соответствует два набора неизвестных (х; у; z): (7; 10; 17) и (14; 21; 28).

Ответ: (7; 10; 17), (14; 21; 28)

Теперь решим более трудные задачи.

Задача 6. Тёма сделал несколько мелких покупок в супермаркете, имея при себе 100 рублей. Давая сдачу с этой суммы, кассир ошиблась, перепутав местами цифры, и выплатила рублями то, что должна была вернуть копейками, и, наоборот, копейками то, что полагалось вернуть рублями. Купив в аптеке набор пипеток за 1 руб. 40 коп., Тема обнаружил ошибку кассира и, пересчитав деньги, нашел, что оставшаяся у него сумма втрое превышает ту, которую ему должны были вернуть в супермаркете. Какова стоимость всех покупок Темы?

Решение. Пусть правильная сдача равна nруб. и т коп., то есть (100n+ т) коп. Реально кассирша выплатила сумму т руб. и nкоп., то есть (100m + n) коп. После покупки пипеток у Темы останется (100т + n—140) коп. По условию эта сумма в три раза больше, чем 100n + т. Это дает следующее уравнение для неизвестных nи т:

100т + n - 140 - 3 • (100n + т)

97m– 299m - 140. (8)

Поскольку число копеек не может быть больше, чем 99, справедливо двойное неравенство: 1 ≤ n, m ≤ 99. Оно, в частности, влечет, что сдача не превышает первоначальную сумму в 100 рублей, которая была у Темы.

Хотя уравнение (8) является стандартным уравнением в целых числах вида ах + by = с, найти его частное решение (чтобы свести дело к однородному уравнению) простым подбором весьма непросто. На этом примере мы продемонстрируем общий метод поиска частного решения (алгоритм Евклида), который автоматически приводит к успеху.

Рассмотрим коэффициенты при неизвестных (а = 97 и b= 299) и разделим больший коэффициент на меньший. В результате получим неполное частное 3 и остаток 8. Иначе говоря, справедливо равенство 299 = 3•97 + 8, или, что то же самое, 8 = 299 -3•97.

Теперь заменим больший коэффициент (то есть 299) на остаток (то есть 8) и проделаем с парой 97, 8 ту же процедуру: разделим 97 на 8. В результате мы получим неполное частное 12 и остаток 1. Иначе говоря, справедливо равенство 97 = 12•8 + 1, или, что то же самое, 1 = 97 — 12•8. Заменим в этом равенстве число 8 выражением 299 – 3 • 97, найденным в предыдущем абзаце:

1 = 97-12• (299 – 3 • 97) = 37 • 97 – 12 • 299.

Итак, мы представили число 1 (это наибольший общий делитель чисел 97 и 299) в виде линейной комбинации чисел 97 и 299. Умножая последнее равенство на 140, мы получим искомое частное решение уравнения (8): т₀= 37 • 140 = 5180, п₀= 12 • 140 = 1680.

Это частное решение обычным образом приводит к следующему общему решению уравнения (8) в целых числах:

Условия 1 < n, т ≤99 однозначно определяют значение параметра k: k= -17, что приводит к следующим значениям основных неизвестных n и m=31, m=97.

Поэтому стоимость всех покупок Темы (в рублях) равна

100-31,97+1,40 = 69,43.

Проблему с поиском частного решения можно обойти с помощью следующего способа решения уравнения (8) (этот метод работает длялюбого уравнения вида ах+by=с и всущности является вариантом алгоритма Евклида).

Выразим неизвестную с меньшим коэффициентом (в нашем случае — это т) через другую неизвестную:

И выделим целую часть из дробей

, ,

Введем новую неизвестную т₁(вместо т) по формуле т₁= т - Зn-1. Для нее последнее равенство примет вид:

97m₁ = 8n + 43.

Это уравнение имеет тот же вид, что и исходное. Применим к нему процедуру, описанную в предыдущем абзаце: выразим неизвестную с меньшим коэффициентом (в нашем случае — это n) через другую неизвестную:

и выделим целую часть из дробей

,

Введем новую переменную n₁(вместо n) по формуле n₁= n₁- 12т₁ + 5. Для нее последнее равенство примет вид:

8n₁ = т₁-3.

Поскольку коэффициент при т₁равен 1, общее решение этого уравнения в целых числах есть:

.

Возвращаясь к основным неизвестным /гит, мы получим общее решение в целых числах уравнения (8)

При l=k+17 мы получим общее решение уравнения (8), найденное ранее.

Описанный метод решения линейных диофантовых уравнений был известен уже математикам Древней Индии; они называли его «метод рассеивания».

Ответ: 69 руб. 43 коп.

Задача 7. Длина дороги, соединяющей пункты А и В, равна 2 км. По этой дороге курсируют два автобуса. Достигнув пункта А или пункта В, каждый из автобусов немедленно разворачивается и следует без остановок к другому пункту. Первый автобус движется со скоростью 51 км/ч, а второй — со скоростью 42 км/ч. Сколько раз за 8 часов движения автобусы

а) встретятся в пункте В;

б) окажутся в одном месте строго между пунктами А и В,

если известно» что первый стартует из пункта А, а второй — из пункта В?

Решение. Примем момент старта автобусов в качестве начального

и обозначим через t'_n , t’_nмоменты времени, когда первый и второй автобусы в n-й раз окажутся в пункте В.

Поскольку первый автобус стартует из пункта А, к моменту n-говизита в В он пройдет путь s_п= 2 + 4(n -1) = 4n- 2 (последовательность s^’_nобразует арифметическую прогрессию с разностью 4).

Поэтому t’_n=

.

Второй автобус к моменту n-визита в пункт В пройдет путь s’_n = 4(n-1) = 4n-4 (последовательность s’_nтакже будет арифметической прогрессией с разностью 4). Поэтому t’_n =

.

Встреча автобусов в пункте В означает, что для некоторых натуральных nи т верно равенство

T’_n= T’_m

14n-17m=-10