Теория решения диофантовых уравнений. Однородные уравнения. Общие линейные уравнения. Единственности разложения натурального числа на простые множители. Решение каждой конкретной задачи в целых числах с помощью разных методов. Основные неизвестные х и у.
Аннотация к работе
Наибольший общий делитель чисел а = 80 и b = 126 равен 2, и после сокращения на 2 мы получим уравнение Если числа а и b - взаимно простые, то уравнение ах by = 0 имеет бесконечно много решений в целых числах, которые находятся во взаимно однозначном соответствии с множеством целых чисел Z (то есть могут быть занумерованы целыми числами) и описываются формулой: хп = bn, yn =-an, где n Z - «номер» решения. Если наибольший общий делитель d коэффициентов а и b больше 1, а свободный член с не делится на d, то уравнение ах by = с не имеет решений в целых числах. Уравнение ах by = с имеет решение тогда и только тогда, когда число с входит в область значений М функции f(x; у) = ах by от двух целочисленных аргументов х, у. Если числа а и b - взаимно простые, то уравнение ах by = с имеет бесконечно много решений в целых числах, которые находятся во взаимно однозначном соответствии с множеством целых чисел Z (то есть могут быть занумерованы целыми числами) и описываются формулой: xn = х0 bn, yn = y0 - an, где n Z - «номер» решения, а х0, у0 - частное решение (которое существует в силу теоремы 3).
Введение
Линейным диофантовым уравнением называется уравнение с несколькими неизвестными вида а1х1 ... anxn = с, где (известные) коэффициенты а1,..., an и с - целые числа, а неизвестные х1, …xn также являются целыми числами. К решению подобных уравнений сводятся разнообразные текстовые задачи, в которых неизвестные величины выражают количество предметов того или иного рода и потому являются натуральными (или неотрицательными целыми) числами.
Теория решения подобных уравнений является классическим разделом элементарной математики. В ней не приходится писать сложные и громоздкие формулы, а необходимо проводить аккуратные рассуждения, базирующиеся на определенных понятиях теории чисел и связанные в стройную логическую конструкцию. В рамках этой теории можно дать исчерпывающее решение рассматриваемого класса задач с четко описанным алгоритмом получения ответа.
Конкретные задачи такого рода были решены еще в Древнем Вавилоне около 4 тысяч лет тому назад. Древнегреческий мыслитель Диофант, который жил около 2 тысяч лет тому назад, в своей книге «Арифметика» решил большое число таких и более сложных уравнений в целых числах и в сущности описал общие методы их решения.
В школьных учебниках эта тема затрагивается вскользь, да и то лишь в 8-м классе, в то время как задачи, где требуется решать уравнения описанного типа, относительно часто предлагаются на вступительных экзаменах.
В настоящей брошюре на примерах решения конкретных экзаменационных задач МГУ им. М.И. Ломоносова мы расскажем об основных результатах и методах теории линейных диофантовых уравнений. Поскольку, за редким исключением, на экзаменах предлагаются уравнения с двумя неизвестными, мы ограничимся этим случаем, то есть будем рассматривать уравнения вида ах Ьу = с. Это позволит упростить теоретические рассмотрения, не ограничивая, в сущности, общности описываемых методов (мы продемонстрируем это в задаче 13 на примере конкретного уравнения вида ах Ьу cz = d.
Следует отметить, что каждая конкретная задача в целых числах может решаться с помощью разных методов. Целью нашей работы является демонстрация возможностей теории линейных диофантовых уравнений.
Однородные уравнения
Прежде всего, мы рассмотрим однородные линейные уравнения, то есть уравнения вида ах by = 0, все члены которых являются одночленами первой степени.
Если коэффициенты а и Ь имеют общий делитель d, то обе части уравнения ах by = 0 можно сократить на d. Поэтому, не нарушая общности, можно считать, что числа а и b - взаимно простые.
Рассмотрим, например, уравнение 80х 126y = 0.
Разложим коэффициенты а = 80 и b=126 на простые множители: а = 24 • 5, b = 2 • З2 • 7. Наибольший общий делитель чисел а = 80 и b = 126 равен 2, и после сокращения на 2 мы получим уравнение
40x 63y = 0, (1) в котором коэффициенты а = 40 = 23 • 5 и b = 63 = З2 • 7 являются взаимно простыми целыми числами.
Разложение на простые множители коэффициентов уравнения, которое мы использовали для сокращения на наибольший общий делитель, можно использовать и для завершения решения. Перепишем уравнение (1) в виде: 23•5•х = -32•7•у.(2)
Левая часть уравнения (2) делится на 23 • 5. Поэтому и правая часть, которая равна левой, должна делиться на 23 • 5, а это возможно тогда и только тогда, когда неизвестная у делится на 23 • 5: у = 23 • 5 • u = 40u,(3) где и - некоторое целое число.
Аналогичные рассуждения применимы и к правой части уравнения (2). Правая часть делится на
З2 • 7. Поэтому и левая часть, которая равна правой, должна делиться на З2 • 7, а это возможно тогда и только тогда, когда неизвестная х делится на З2 • 7: x = З 2 • 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, yn = -an, где n Z - «номер» решения.
Эта теорема часто встречается при решении разнообразных задач на целые числа, и мы рекомендуем абитуриентам запомнить ее формулировку.
В качестве простого примера применения теоремы 1 рассмотрим следующую задачу.
Задача 1. Найти все целочисленные решения уравнения х2 5y2 34z2 2ху - 10xz - 22yz - 0.
Решение. Рассмотрим уравнение х2 5у2 34z2 2ху - 10xz - 22yz = 0 как квадратное уравнение относительно одной неизвестной х: х2 2х(у - 5г) by2 34z2 - 22yz = 0.
Тогда = (y-5z)2-(5y2 34z2-22yz)=-(2y-3z)2.
Если это уравнение имеет решение, то дискриминант должен быть неотрицательным, что возможно только в случае 2у - 3z = 0. Тогда дискриминант равен нулю, и уравнение имеет единственное решение х = 5z- у.
Итак, исходное уравнение равносильно системе
Общее решение первого уравнения в целых числах дается формулами у = Зn, z = 2n, где n Z. Из второго уравнения теперь можно найти х (причем х автоматически будет целым числом): х = In.
Таким образом, исходное уравнение имеет бесконечно много целочисленных решений, которые могут быть описаны формулой (х; у; z) - (7n; Зn; 2n), n Z.
Ответ: (х; у, z) = (7n; Зn; 2n), n e Z.
Общие линейные уравнения
В этом разделе мы будем рассматривать диофантовы уравнения вида ах by = с.
Прежде всего отметим, что, вообще говоря, такое уравнение может и не иметь целочисленных решений.
Действительно, допустим, что уравнение ах by = с имеет решение. Если коэффициенты а и b имеют общий делитель d > 1, то число ах by, которое стоит в левой части, можно без остатка разделить на d. Поэтому и правую часть уравнения, то есть свободный член с, можно без остатка разделить на d. Иначе говоря, справедлива следующая теорема.
Теорема 2. Если наибольший общий делитель d коэффициентов а и b больше 1, а свободный член с не делится на d, то уравнение ах by = с не имеет решений в целых числах.
Это простое утверждение часто используется, например, для доказательства иррациональности чисел, записанных с помощью радикалов.
Задача 2. Доказать, что число не является рациональным числом.
Решение. Допустим противное, что - число рациональное.
Тогда существуют натуральные т, п такие, что .
Избавляясь от радикала и дроби, получим: 2n3 = т3(5)
Разложим числа т и n на простые множители (мы явно указываем только простой множитель 2): т = 2х•... n = 2y•... где х, у - неотрицательные целые числа (отсутствие простого множителя 2 в разложении означает, что соответствующий показатель степени равен нулю).
Тогда равенство (5) примет вид: 23y 1•... = 23х•...
В силу единственности разложения натурального числа на простые множители
Зу 1 = 3x 3(х - у) = 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; у), это множество имеет вид: {..., -и2, -п1, 0, n1, n2,...}, где n1 < n2 < ... - натуральные числа.
Рассмотрим наименьшее положительное число из М, то есть n1 и докажем, что оно равно 1. Для этого разделим число |а| на n1 с остатком, то есть найдем такие целые числа q (неполное частное) и r (остаток), что |а| = n1q r, причем 0 r п . Поскольку число n1 принадлежит множеству М, для некоторых целых х0 и у0 верно равенство n] = ах0 by0. Кроме того, | а | = sgn (a) • а, где sgn(а) = 1, если а > О, и sgn(а) = -1, если а < 0.
Тогда г = | а | - n1g = sgn (а) •а - (ах0 by0) -q = ax by, где x: = sgn(а) - x0q, у = -y0q - некоторые целые числа. Поэтому неотрицательное целое число г также принадлежит множеству М. Если бы число г было положительным, то условие 0 < r < n , которому удовлетворяет г как остаток от деления на л,, означало бы, что в множестве М есть положительное число, меньшее, чем n1 чего быть не может. Значит, r = 0, то есть | а| (а вместе с ним и а) делится без остатка на n1.
Аналогичные рассуждения показывают, что и b делится без остатка на n1. Следовательно, n1 - общий делитель чисел а и b, a поскольку эти числа взаимно простые, число n1 равно 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, 2d, ...}.
Доказательство. Так как d = НОД(а; b), числа а и b можно записать в виде: а = da", b = db", причем числа а", b" - взаимно простые. Тогда f(x; у) = d •(а"х by). В силу теоремы 3, любое целое число n можно представить в виде а"х b"у. Поэтому множество чисел, которые могут быть записаны в виде ах by, есть {..., -2d, -d, 0, d, 2d, ...}.
Приведенное доказательство теоремы 3 дает удобный метод нахождения частного (то есть конкретного) решения при решении конкретных уравнений вида ах by = с (если а и b взаимно простые целые числа): 1) нужно образовать две последовательности чисел: -..., -2а, -а, О, а, 2а, ... и -..., -2b, -b, О, b, 2b, ...
(обычно достаточно выписать по несколько членов в обе стороны), и расположить их друг под другом так, чтобы положительные члены одной стояли под отрицательными членами другой;
2) затем в уме находить всевозможные суммы пар членов этих последовательностей, пока не найдем пару, дающую в сумме с.
Рассмотрим, например, уравнение 2х - by =1. Выпишем ряды чисел, кратных коэффициентам а = 2 и b = -5: Из этой таблицы ясно, что второе число из первой строки (то есть -4), которое соответствует х = -2, и третье число из второй строки (то есть 5), которое соответствует у = -1, и дают в сумме 1. Таким образом, уравнение 2х- by = 1 имеет частное решение х0 = -2, у0 = -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)
Чтобы решить это уравнение, прежде всего, найдем какое-нибудь частное решение в целых (не обязательно неотрицательных) числах. Мы это уже сделали выше, когда разбирали пример, иллюстрирующий метод поиска частных решений линейных диофантовых уравнений; в нашем случае в качестве такого частного решения можно взять, например, х0 =-2, y0 =-1, так что верно равенство
Общее решение этого уравнения в целых числах имеет вид: х 2 = 5k, у 1 = 2k, где k - произвольное целое число. Чтобы числа х и у были неотрицательными, параметр k должен быть натуральным числом. Теперь для числа n имеем: n = 6х 4 = 6(5k - 2) 4 = 30k - 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 - т) руб. По условию задачи эти величины равны: 7n 10m = 4(20 - n) 9(20 - т) 11n 19m = 260.
Решим уравнение 11n 19m = 260: 1. Найдем частное решение; им будет, например, n0 = 15, т0 = 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, где k Z.
Поскольку n, т ? 0, параметр k может быть равен только нулю. Поэтому найденное частное решение будет единственным решением исходного уравнения в неотрицательных целых числах: n = 15, т = 5. Так как это решение, кроме того, удовлетворяет условию n, m ? 20, найденное значение m = 5 и будет ответом задачи.
Ответ: 5 стаканов.
Практически дословное повторение рассуждений, проведенных при решении задач 3 и 4, позволяет доказать, что общее решение уравнения ах by = с представляет собой сумму частного решения (х0 ; у0) этого уравнения и общего решения соответствующего однородного уравнения ах by = 0. Отсюда, в свою очередь, вытекает следующая важная общая теорема.
Теорема 5. Если числа а и b - взаимно простые, то уравнение ах by = с имеет бесконечно много решений в целых числах, которые находятся во взаимно однозначном соответствии с множеством целых чисел Z (то есть могут быть занумерованы целыми числами) и описываются формулой: xn = х0 bn, yn = y0 - an, где n Z - «номер» решения, а х0, у0 - частное решение (которое существует в силу теоремы 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): т0 = 37 • 140 = 5180, п0 = 12 • 140 = 1680.
Это частное решение обычным образом приводит к следующему общему решению уравнения (8) в целых числах: Условия 1 < n, т ?99 однозначно определяют значение параметра k: k = -17, что приводит к следующим значениям основных неизвестных n и m=31, m=97.
Поэтому стоимость всех покупок Темы (в рублях) равна
100-31,97 1,40 = 69,43.
Проблему с поиском частного решения можно обойти с помощью следующего способа решения уравнения (8) (этот метод работает для любого уравнения вида ах by=с и в сущности является вариантом алгоритма Евклида).
Выразим неизвестную с меньшим коэффициентом (в нашем случае - это т) через другую неизвестную:
И выделим целую часть из дробей , , Введем новую неизвестную т1 (вместо т) по формуле т1 = т - Зn -1. Для нее последнее равенство примет вид: 97m1 = 8n 43.
Это уравнение имеет тот же вид, что и исходное. Применим к нему процедуру, описанную в предыдущем абзаце: выразим неизвестную с меньшим коэффициентом (в нашем случае - это n) через другую неизвестную: и выделим целую часть из дробей , Введем новую переменную n1 (вместо n) по формуле n1 = n1 - 12т1 5. Для нее последнее равенство примет вид: 8n1 = т1-3.
Поскольку коэффициент при т1 равен 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
Рассмотрим его как уравнение относительно п и т и решим его.
В качестве частного решения можно взять, например, n0 = 9, m0 = 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: tk = .
Число встреч за 8 часов равно числу решений неравенства tk ? 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) = 4n - 2 (последовательность S”n также будет арифметической прогрессией с разностью 4). Поэтому T”n= .
Встреча автобусов в пункте А означает, что для некоторых натуральных n и т верно равенство
T’n= T”n 28n-34m=11
Левая часть этого уравнения - четное число, а правая - нет. Поэтому оно не имеет решений в целых числах. Следовательно, автобусы никогда не встретятся в пункте А.
Теперь перейдем непосредственно к решению второй части задачи. Для этого введем систему координат на дороге между А и В, выбрав в качестве начала отсчета пункт А, в качестве положительного направления - направление от А к В (рис. 2).
Пусть x1(t), x2(t) - координаты первого и второго автобусов соответственно в момент t. Графики функций x1(t) и x2(t) - это ломаные линии, изображенные на рисунках 1 и 2 соответственно. Первая ломаная состоит из 102 пар звеньев с угловыми коэффициентами 51 и -51, а вторая - из 84 пар звеньев с угловыми коэффициентами 42 и -42 (на рисунках мы исказили масштаб). Точки А и В на оси ординат имеют координаты 0 и 2 соответственно и соответствуют прохождению через пункты А и В.
Встреча автобусов в какой-то момент t означает совпадение их координат в этот момент: x1(t) = x2(t), то есть пересечение графиков функций x1(t) и x2(t).
Каждое звено первой ломаной пересекает вторую ломаную ровно в одной точке. Поэтому всего будет 102 точки пересечения возрастающих звеньев первой ломаной со второй ломаной и 102 точки пересечения убывающих звеньев первой ломаной со второй ломаной. Поскольку автобусы не встречаются в пункте А, ни одна из этих точек не будет лежать на оси абсцисс. С другой стороны, поскольку автобусы встречаются 6 раз в пункте В, ровно 6 точек пересечения будет лежать на горизонтальной прямой у = 2. Эти точки будут включены как в 102 точки пересечения возрастающих звеньев первой ломаной со второй ломаной, так и в 102 точки пересечения убывающих звеньев первой ломаной со второй ломаной. Поэтому число точек пересечения, лежащих внутри полосы 0 < у < 2, равно 2•(102-6)=192