Реферат: Линейные диофантовые уравнения

Введение

Линейным диофантовым уравнением называется уравнение с несколькими неизвестными вида а₁ х₁ + ... + а _n х _n = с, где (известные) коэффициенты а₁ ,..., а _n и с — целые числа, а неизвестные х₁ , … x_n также являются целыми числами. К решению подобных уравнений сводятся разнообразные текстовые задачи, в которых неизвестные величины выражают количество предметов того или иного рода и потому являются натуральными (или неотрицательными целыми) числами.

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

Конкретные задачи такого рода были решены еще в Древнем Вавилоне около 4 тысяч лет тому назад. Древнегреческий мысли­тель Диофант, который жил около 2 тысяч лет тому назад, в своей книге «Арифметика» решил большое число таких и более сложных уравнений в целых числах и в сущности описал общие методы их решения.

В школьных учебниках эта тема затрагивается вскользь, да и то лишь в 8-м классе, в то время как задачи, где требуется решать уравнения описанного типа, относительно часто предлагаются на вступительных экзаменах.

В настоящей брошюре на примерах решения конкретных экза­менационных задач МГУ им. М.И. Ломоносова мы расскажем об основных результатах и методах теории линейных диофантовых уравнений. Поскольку, за редким исключением, на экзаменах предлагаются уравнения с двумя неизвестными, мы ограничим­ся этим случаем, то есть будем рассматривать уравнения вида

ах + Ьу = с. Это позволит упростить теоретические рассмотрения, не ограничивая, в сущности, общности описываемых методов (мы продемонстрируем это в задаче 13 на примере конкретного уравне­ния вида ах + Ьу + сz = d.

Следует отметить, что каждая конкретная задача в целых числах может решаться с помощью раз­ных методов. Целью нашей работы является демонстрация возможностей теории линейных диофан­товых уравнений.

Однородные уравнения

Прежде всего, мы рассмотрим однородные линейные уравнения, то есть уравнения вида

ах + by = 0, все члены которых являются одночленами первой степени.

Если коэффициенты а и Ь имеют общий делитель d , то обе части уравнения ах + by = 0 можно сократить на d . Поэтому, не нарушая общности, можно считать, что числа а и b — взаимно про­стые.

Рассмотрим, например, уравнение 80х + 126y = 0.

Разложим коэффициенты а = 80 и b=126 на простые множители: а = 2⁴ • 5, b = 2 • З² • 7. Наибольший общий делитель чисел а = 80 и b = 126 равен 2, и после сокращения на 2 мы получим уравнение

40x + 63y = 0, (1)

в котором коэффициенты а = 40 = 2³ • 5 и b = 63 = З² • 7 являются взаимно простыми целыми чис­лами.

Разложение на простые множители коэффициентов уравнения, которое мы использовали для сокраще­ния на наибольший общий делитель, можно использовать и для завершения решения. Пере­пишем уравнение (1) в виде:

2³ •5 •х = -3² •7 •у. (2)

Левая часть уравнения (2) делится на 2³ • 5. Поэтому и правая часть, которая равна левой, должна делиться на 2³ • 5, а это возможно тогда и только тогда, когда неизвестная у делится на 2³ • 5:

у = 2³ • 5 • u = 40u,(3)

где и — некоторое целое число.

Аналогичные рассуждения применимы и к правой части урав­нения (2). Правая часть делится на

З² • 7. Поэтому и левая часть, которая равна правой, должна делиться на З² • 7, а это возможно тогда и только тогда, когда неизвестная х делится на З² • 7:

x = З ² • 7 • v = 63v,(4)

где v — некоторое целое число.

Равенства (3) и (4) фактически вводят новые целочисленные неизвестные u , v вместо основных неизвестных х, у. Для новых неизвестных уравнение (2) примет вид: u = - v . Множество решений этого уравнения состоит из бесконечного количества пар:

(-3; 3), (-2; 2), (-1; 1), (0; 0), (1; -1), (2; -2), (3; -3), ...

Иначе говоря, этому уравнению удовлетворяют все пары (-u; u) вида (-n; n), где n — произволь­ное целое число, и только они. Пе­ременная n в этих формулах является своеобразным «номером» решения.

Возвращаясь к основным неизвестным х и у, мы получим, что множество решений уравнения (2) можно записать в виде: х_п = 63n, у = - 40n, где n — произвольное целое число.

Как ясно из приведенного решения (2), оно совершенно не привя­зано к точным значениям коэффициен­тов а и b и не изменится, если вместо чисел а = 40, b = 63 рассмотреть произвольные взаимно про­стые числа. Таким образом, справедлива следующая теорема, которая дает полное решение диофантовых уравнений вида ах + by = 0.

Теорема 1. Если числа а и b — взаимно простые, то уравне­ние ах + by = 0 имеет бесконечно много решений в целых чис­лах, которые находятся во взаимно однозначном соответствии с множест­вом целых чисел Z (то есть могут быть занумерованы целыми числами) и описываются формулой: х_п = bn , y_n = - an , где n Z — «номер» решения.

Эта теорема часто встречается при решении разнообразных за­дач на целые числа, и мы рекомен­дуем абитуриентам запомнить ее формулировку.

В качестве простого примера применения теоремы 1 рассмотрим следующую задачу.

Задача 1 . Найти все целочисленные решения уравне­ния

х² + 5 y ² + 34z² + 2ху - 10 xz - 22у z - 0.

Решение. Рассмотрим уравнение

х² + 5у² + 34z² + 2ху - 10 xz - 22 yz = 0

как квадратное уравнение относительно одной неизвестной х:

х² + 2х(у - 5г) + by ² + 34z² - 22 yz = 0.

Тогда

= ( y -5 z )² -(5 y ² +34 z ² -22 yz )=-(2 y -3 z )² .

Если это уравнение имеет решение, то дискриминант должен быть неотрицательным, что воз­можно только в случае 2у - 3z = 0. Тогда дискриминант равен нулю, и уравнение имеет единствен­ное решение х = 5z- у.

Итак, исходное уравнение равносильно системе

Общее решение первого уравнения в целых числах дается форму­лами у = Зn, z = 2n, где nZ . Из второго уравнения теперь можно найти х (причем х автоматически будет целым числом): х = In .

Таким образом, исходное уравнение имеет бесконечно много целочисленных решений, которые могут быть описаны формулой (х; у; z ) — (7n; Зn; 2n), n Z .

Ответ: (х; у, z ) = (7n; Зn; 2 n), n eZ .

Общие линейные уравнения

В этом разделе мы будем рассматривать диофантовы уравнения вида ах + by = с.

Прежде всего отметим, что, вообще говоря, такое уравнение может и не иметь целочисленных реше­ний.

Действительно, допустим, что уравнение ах + by = с имеет реше­ние. Если коэффициенты а и b имеют общий делитель d > 1, то число ах + by , которое стоит в левой части, можно без остатка разде­лить на d . Поэтому и правую часть уравнения, то есть свободный член с, можно без остатка разделить на d . Иначе говоря, справедлива следующая теорема.

Теорема 2. Если наибольший общий делитель d коэффициентов а и b больше 1, а свободный член с не делится на d , то уравнение ах + by = с не имеет решений в целых числах.

Это простое утверждение часто используется, например, для доказательства иррациональности чисел, записанных с помощью радикалов.

Задача 2 .Дока­зать, что число не является рациональным числом.

Решение. Допустим противное, что — число рациональное.

Тогда существуют натуральные т, п такие, что .

Избавляясь от радикала и дроби, получим:

2 n ³ = т³ (5)

Разложим числа т иn на простые множители (мы явно указы­ваем только простой множитель 2):

т = 2^х •...

n = 2^y •...

где х, у — неотрицательные целые числа (отсутствие простого мно­жителя 2 в разложении озна­чает, что соответствующий показатель степени равен нулю).

Тогда равенство (5) примет вид:

2^{3 y + 1} •... = 2^3х •...

В силу единственности разложения натурального числа на про­стые множители

Зу + 1 = 3x3(х - у) = 1.

Последнее уравнение является линейным диофантовым уравнени­ем вида ах + Ьу = с, причем коэффи­циенты а = 3, b = -3 делятся на 3, в то время как свободный член с = 1 — нет. Значит, это уравнение не имеет целочисленных решений, что означает ложность исходного предположения о рациональности числа.

.Будем теперь рассматривать только такие уравнения вида ах + by = с, в которых свободный член с делится на d = НОД(а; b ). После деления обеих частей уравнения на d мы получим уравнение того же вида, но уже со взаимно простыми коэффициентами при неизвестных. Только такие уравнения мы будем рассматривать ниже в этом разделе.

В этом случае со стороны теоремы 2 нет препятствий к тому, что­бы уравнение имело целочислен­ные решения. Но отсюда, конечно, не следует, что решения обязаны быть.

На самом деле ответ на этот вопрос положительный.

Теорема 3 . Любое уравнение ах + by = с, где НОД(а; b ) = 1, имеет хотя бы одно решение в целых числах.

Доказательство. Уравнение ах + by = с имеет решение тогда и только тогда, когда число с входит в область значений М функции f ( x ; у) = ах + by от двух целочисленных аргументов х, у. Поэтому наша теорема фактически утверждает, что М = Z . Именно этот факт мы и будем доказывать.

Прежде всего отметим, что множество М содержит бесконечно мно­го чисел, например, 0= f (0; 0), а = f (1; 0), -а = f (-1; 0), а + b = f (1; 1) и т.д. Поскольку f (- x ; -у) = - f ( x ; у), это множество имеет вид:

{..., -и₂ , -п_1, 0, n ₁ , n ₂ , ...},

где n ₁ < n ₂ < ... — натуральные числа.

Рассмотрим наименьшее положительное число из М, то есть n ₁ и докажем, что оно равно 1. Для этого разделим число |а| на n ₁ с остатком, то есть найдем такие целые числа q (неполное частное) и r (остаток), что |а| = n ₁ q + r, причем 0 rп . Поскольку число n ₁ принадлежит множеству М, для некоторых целых х₀ и у₀ верно равенство n _] = ах₀ + b у₀ . Кроме того,

| а | = sgn (a) • а,

где sgn(а) = +1, если а > О, и sgn(а) = -1, если а < 0.

Тогда

г = | а | - n₁ g = sgn (а) •а - (ах₀ + by ₀ ) - q = ax + by ,

где x: = sgn(а) - x ₀ q , у = -y₀ q — некоторые целые числа. Поэтому неотрицательное целое число г также принадлежит множеству М. Если бы число г было положительным, то условие 0 < r < n , кото­рому удовлетворяет г как остаток от деления на л,, означало бы, что в множестве М есть положительное число, меньшее, чем n ₁ чего быть не может. Значит, r = 0, то есть | а| (а вместе с ним и а) делится без остатка на n₁ .

Аналогичные рассуждения показывают, что и b делится без остатка на n ₁ . Следовательно, n ₁ — общий делитель чисел а и b , a поскольку эти числа взаимно простые, число n ₁ равно 1.

Функция f ( x ; y ) = ax + by обладает свойством: f ( kx ; ky ) = k • f ( x ; у). Поэтому если некоторое число с М, то и число kc M . Как мы установили, 1 М. Значит, и любое целое число k входит в М, то есть М = Z . Это и означает справедливость нашей теоремы.

Имея в виду более сложные задачи, мы в качестве простого следствия из доказанной теоремы 3 получим еще одну важную теорему.

Теорема 4. Если числа а и b — целые, то множество значений функции f ( x ; y ) = ax + by от двух целочис­ленных аргументов х и у совпадает с множеством чисел, кратных d = НОД(а; b ), то есть с множеством {..., —2d, — d , 0, d , 2 d , ...}.

Доказательство. Так как d = НОД(а; b ), числа а и b можно запи­сать в виде: а = da ', b = db ', причем числа а', b ' — взаимно простые. Тогда f ( x ; у) = d •(а'х + b у). В силу теоремы 3, любое целое число n можно представить в виде а'х + b 'у. Поэтому множество чисел, которые могут быть записаны в виде ах + by , есть {..., -2d, - d , 0, d , 2 d , ...}.

Приведенное доказательство теоремы 3 дает удобный метод нахождения частного (то есть конкрет­ного) решения при решении конкретных уравнений вида ах + by = с (если а и b взаимно простые целые числа):

1) нужно образовать две последовательности чисел:

-..., -2а, -а, О, а, 2а, ... и -..., -2 b , - b , О, b , 2 b , ...

(обычно достаточно выписать по несколько членов в обе стороны), и расположить их друг под другом так, чтобы положительные члены одной стояли под отрицательными членами другой;

2) затем в уме находить всевозможные суммы пар членов этих последовательностей, пока не най­дем пару, дающую в сумме с.

Рассмотрим, например, уравнение 2х - b у =1. Выпишем ряды чисел, кратных коэффициентам а = 2 и b = -5:

Из этой таблицы ясно, что второе число из первой строки (то есть -4), которое соответствует х = -2, и третье число из второй строки (то есть 5), которое соответствует у = -1, и дают в сумме 1. Та­ким образом, уравнение 2х- b у = 1 имеет частное решение х₀ = -2, у₀ = -1. Конечно, эту пару можно найти и проще, просто подставляя в исходное урав­нение в уме небольшие числа с тем, чтобы полу­чить верное равенст­во. Для несложных уравнений обычно поступают именно так.

В ряде случаев приходится выписывать довольно много (несколь­ко десятков) членов последовательно­стей ах и by . Тогда, конечно, описанный прием не очень удобен, так как требует больших затрат времени. В этой ситуации обычно рекомендуют использовать ал­горитм Евклида для нахождения наибольшего общего делителя коэффициентов а и b (само доказательство замечатель­ной теоремы 3 также может быть получено с помощью алгоритма Евклида). Мы продемонст­рируем этот алгоритм при решении задачи 6.

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

Задача 3. Остаток от деления некоторого натурального числа n на 6 равен 4, остаток от деления n на 15 равен 7. Чему равен остаток от деления n на 30?

Решение. Тот факт, что остаток от деления числа n на 6 равен 4, означает, что существует неотри­цательное целое х такое, что n = 6х + 4. Аналогично, существует неотрицательное целое y такое, что n = 15у + 7. Исключая из этих равенств число n, для х и у получим уравнение

2х-бу-1. (6)

Чтобы решить это уравнение, прежде всего, найдем какое-нибудь частное решение в целых (не обязательно неотрицательных) числах. Мы это уже сделали выше, когда разбирали пример, иллюстрирую­щий метод поиска частных решений линейных диофантовых урав­нений; в нашем случае в качестве такого частного решения можно взять, например, х₀ =- 2, y ₀ = -1, так что верно равенство

2• (-2)-5• (-1)=1. (7)

Вычитая из уравнения (в) равенство (7), получим:

2(х + 2) = 5( y + 1).

Общее решение этого уравнения в целых числах имеет вид:

х + 2 = 5 k , у + 1 = 2 k ,

где k — произвольное целое число. Чтобы числа х и у были неотри­цательными, параметр k должен быть натуральным числом. Теперь для числа n имеем:

n = 6х + 4 = 6(5 k - 2) + 4 = 30 k - 8 = 30( k - 1) + 22.

Поскольку целое число (k — 1 ) неотрицательно, это равенство означает, что остаток от деления n на 30 равен 22.

Ответ: 22.

Задача 4. Фирма продавала чай в центре города по 7 руб., а кофе по 10 руб. за стакан; на вокзале — по 4 руб. и 9 руб. соответственно. Всего было продано за час 20 стаканов чая и 20 стаканов кофе, при этом выручка в центре и на вокзале оказалась одинаковой. Сколько стаканов кофе было продано в центре?

Решение. Пусть n и т соответственно — количество стаканов чая и кофе, проданных в центре города. Тогда количество стаканов чая и кофе, проданных на вокзале, будет равно 20 - n и 20 — т соответ­ственно. По смыслу задачи переменные n и т — неотрицательные целые числа, не превосходящие 20: n, т = 0,1,..., 20.

Общая выручка в центре равна 7n + 10m руб., а на вокзале равна 4(20 — n ) + 9(20 — т) руб. По условию задачи эти величины равны:

7 n + 10 m = 4(20 - n ) + 9(20 - т) 11 n + 19 m = 260.

Решим уравнение 11n + 19m = 260:

1. Найдем частное решение; им будет, например, n ₀ = 15, т₀ = 5.

2. Вычитая из равенства 11n + 19m = 260равенство 11 • 15 +19 • 5= 260, мы получим однородное уравнение: 11(n- 15) = 19(5 - m).

3. Общее решение этого однородного уравнения в целых числах имеет вид:

n-15=19k, 5-m=11k,

где k Z. Соответственно, общее решение исходного уравнения в целых числах имеет вид:

n = 15 + 19k, т = 5 – 11k,

где kZ.

Поскольку n , т ≥ 0, параметр k может быть равен только нулю. Поэтому найденное частное решение будет единственным решени­ем исходного уравнения в неотрицательных целых числах: n = 15, т = 5. Так как это решение, кроме того, удовлетворяет условию n, m≤ 20, найденное значение m = 5 и будет ответом задачи.

Ответ: 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 11 x – 7 y = 7

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

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

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

8 n ₁ = т₁ -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) = 4 n - 2 (последователь­ность s ^’ _n образует арифметическую прогрессию с разностью 4).

Поэтому t ’ _n = .

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

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

T ’ _n = T ’ _m 14 n -17 m =-10

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

В качестве частного решения можно взять, например, n ₀ = 9, m₀ = 8:

14 • 9-17 • 8 = -10.

Вычитая это равенство из уравнения 14n — 17m = -10, мы полу­чим однородное уравнение:

14(n-9) = 17(m-8).

Его общее решение в целых числах имеет вид: n - 9 = 17k, т - 8 = 14k, где k Z . Отсюда

n = 9 + 17k, m = 8 + 14k. Поскольку нас интересует решение в натуральных числах, возможные значения целочислен­ного параметра k должны быть неотрицательными: k Z . Пере­менную k можно интерпретировать как номер встречи автобусов в пункте В (имея в виду, что встречи нумеруются не с 1, а с 0). Моментk-й встречи можно подсчитать как t ’ _n при n = 9 + 17k: t_k = .

Число встреч за 8 часов равно числу решений неравенства t_k ≤ 8 на множестве k Z :

Таким образом, за 8 часов автобусы ровно 6 раз встретятся в пункте В.

Перейдем теперь ко второй части задачи («сколько раз за 8 часов автобусы окажутся в одном месте строго между пунктами А и В? »). Прежде всего найдем, сколько раз за 8 часов автобусы встретятся в пункте А — эта информация окажется позже нам полезной.

Как и в предыдущем исследовании, примем момент старта авто­бусов в качестве начального и обозначим через T ’ _n , T " _n — моменты времени, когда первый и второй автобусы в n -й раз окажутся в пункте-А (рис. 1).

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

Поэтому

T’_n =.

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

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

T ’ _n = T ” _n 28 n -34 m =11

Левая часть этого уравнения — четное число, а правая — нет. Поэтому оно не имеет решений в целых числах. Следовательно, автобусы никогда не встретятся в пункте А.

Теперь перейдем непосредственно к решению второй части за­дачи. Для этого введем систему координат на дороге между А и В, выбрав в качестве начала отсчета пункт А, в качестве положитель­ного направления — направление от А к В (рис. 2).

Пусть x ₁ ( t ), x ₂ ( t ) — координаты первого и второго автобусов соот­ветственно в момент t . Графики функций x ₁ ( t ) и x ₂ ( t ) — это ломаные линии, изображенные на рисунках 1 и 2 соответственно. Первая ломаная состоит из 102 пар звеньев с угловыми коэффициентами 51 и -51, а вторая — из 84 пар звеньев с угловыми коэффициентами 42 и -42 (на рисунках мы исказили масштаб). Точки А и В на оси ординат имеют координаты 0 и 2 соответственно и соответствуют прохождению через пункты А и В.

Встреча автобусов в какой-то момент t означает совпадение их координат в этот момент: x ₁ ( t ) = x ₂ ( t ), то есть пересечение графиков функций x ₁ ( t ) и x ₂ ( t ).

Каждое звено первой ломаной пересекает вторую ломаную ровно в одной точке. Поэтому всего будет 102 точки пересечения возрас­тающих звеньев первой ломаной со второй ломаной и 102 точки пе­ресечения убывающих звеньев первой ломаной со второй ломаной. Поскольку автобусы не встречаются в пункте А, ни одна из этих точек не будет лежать на оси абсцисс. С другой стороны, поскольку авто­бусы встречаются 6 раз в пункте В, ровно 6 точек пересечения будет лежать на горизонтальной прямой у = 2. Эти точки будут включены как в 102 точки пересечения возрастающих звеньев первой ломаной со второй ломаной, так и в 102 точки пересечения убывающих звеньев первой ломаной со второй ломаной. Поэтому число точек пересече­ния, лежащих внутри полосы 0 < у < 2, равно

2•(102-6)=192

Ответ: а) 6 раз; б) 192 раза.