Введение
Линейным диофантовым уравнением называется уравнение с несколькими неизвестными вида а1
х1
+ ... + а
n
х
n
= с,
где (известные) коэффициенты а1
,..., а
n
и с
— целые числа, а неизвестные х1
, …
xn
также являются целыми числами. К решению подобных уравнений сводятся разнообразные текстовые задачи, в которых неизвестные величины выражают количество предметов того или иного рода и потому являются натуральными (или неотрицательными целыми) числами.
Теория решения подобных уравнений является классическим разделом элементарной математики. В ней не приходится писать сложные и громоздкие формулы, а необходимо проводить аккуратные рассуждения, базирующиеся на определенных понятиях теории чисел и связанные в стройную логическую конструкцию. В рамках этой теории можно дать исчерпывающее решение рассматриваемого класса задач с четко описанным алгоритмом получения ответа.
Конкретные задачи такого рода были решены еще в Древнем Вавилоне около 4 тысяч лет тому назад. Древнегреческий мыслитель Диофант, который жил около 2 тысяч лет тому назад, в своей книге «Арифметика» решил большое число таких и более сложных уравнений в целых числах и в сущности описал общие методы их решения.
В школьных учебниках эта тема затрагивается вскользь, да и то лишь в 8-м классе, в то время как задачи, где требуется решать уравнения описанного типа, относительно часто предлагаются на вступительных экзаменах.
В настоящей брошюре на примерах решения конкретных экзаменационных задач МГУ им. М.И. Ломоносова мы расскажем об основных результатах и методах теории линейных диофантовых уравнений. Поскольку, за редким исключением, на экзаменах предлагаются уравнения с двумя неизвестными, мы ограничимся этим случаем, то есть будем рассматривать уравнения вида
ах + Ьу = с. Это позволит упростить теоретические рассмотрения, не ограничивая, в сущности, общности описываемых методов (мы продемонстрируем это в задаче 13 на примере конкретного уравнения вида ах + Ьу + сz = 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
+ 5
y
2
+
34z2
+ 2ху - 10
xz
- 22у
z
- 0.
Решение.
Рассмотрим уравнение
х2
+ 5у2
+
34z2
+ 2ху - 10
xz
- 22
yz
=
0
как квадратное уравнение относительно одной неизвестной х:
х2
+ 2х(у
- 5г) + by
2
+
34z2
- 22
yz
=
0.
Тогда
= (
y
-5
z
)2
-(5
y
2
+34
z
2
-22
yz
)=-(2
y
-3
z
)2
.
Если это уравнение имеет решение, то дискриминант должен быть неотрицательным, что возможно только в случае 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
3
= т3
(5)
Разложим числа т
иn
на
простые множители (мы явно указываем только простой множитель 2):
т = 2х
•...
n = 2y
•...
где х, у
— неотрицательные целые числа (отсутствие простого множителя 2 в разложении означает, что соответствующий показатель степени равен нулю).
Тогда равенство (5) примет вид:
23
y
+
1
•... = 23х
•...
В силу единственности разложения натурального числа на простые множители
Зу +
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
; у),
это множество имеет вид:
{..., -и2
, -п1,
0, n
1
,
n
2
,
...},
где n
1
<
n
2
<
... — натуральные числа.
Рассмотрим наименьшее положительное число из М,
то есть n
1
и докажем, что оно равно 1. Для этого разделим число |а|
на n
1
с остатком, то есть найдем такие целые числа q
(неполное частное) и r (остаток), что |а| =
n
1
q
+ r, причем 0 rп .
Поскольку число n
1
принадлежит множеству М,
для некоторых целых х0
и у0
верно равенство n
]
= ах0
+ b
у0
.
Кроме того,
| а
| = sgn (a) • а,
где sgn(а) = +1, если а >
О, и sgn(а) = -1, если а <
0.
Тогда
г = | а
| - n1
g = sgn (а) •а - (ах0
+ by
0
) -
q
=
ax
+
by
,
где x: = sgn(а) - x
0
q
, у
= -y0
q — некоторые целые числа. Поэтому неотрицательное целое число г также принадлежит множеству М. Если бы число г было положительным, то условие 0 < r < n
, которому удовлетворяет г как остаток от деления на л,, означало бы, что в множестве М
есть положительное число, меньшее, чем n
1
чего быть не может. Значит, r = 0, то есть | а|
(а вместе с ним и а)
делится без остатка на n1
.
Аналогичные рассуждения показывают, что и b
делится без остатка на n
1
.
Следовательно, n
1
— общий делитель чисел а
и b
,
a поскольку эти числа взаимно простые, число n
1
равно 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 имеет частное решение х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, y
0
=
-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
0
= 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,
где kZ.
Поскольку n
, т ≥
0, параметр k может быть равен только нулю. Поэтому найденное частное решение будет единственным решением исходного уравнения в неотрицательных целых числах: n
= 15, т =
5. Так как это решение, кроме того, удовлетворяет условию n, m≤ 20, найденное значение m = 5 и будет ответом задачи.
Ответ:
5 стаканов.
Практически дословное повторение рассуждений, проведенных при решении задач 3 и 4, позволяет доказать, что общее решение уравнения ах +
b
у = с
представляет собой сумму частного решения (х0
; у0
)
этого уравнения и общего решения соответствующего однородного уравнения ах
+ by
= 0. Отсюда, в свою очередь, вытекает следующая важная общая теорема.
Теорема 5. Если числа а и
b
— взаимно простые, то уравнение ах +
by
= с имеет бесконечно много решений в целых числах, которые находятся во взаимно однозначном соответствии с множеством целых чисел
Z
(то есть могут быть занумерованы целыми числами) и описываются формулой: х
n
= х0
+
bn
,
yn
=
y
0
-
an
, где
n
Z
— «номер» решения, а х0
, у0
— частное решение (которое существует в силу теоремы 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): т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
)
через другую неизвестную:
и выделим целую часть из дробей ,
Введем новую переменную n
1
(вместо n) по формуле n
1
= n
1
- 12т1
+
5. Для нее последнее равенство примет вид:
8
n
1
= т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) = 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
0
= 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) = 4
n
- 2 (последовательность S”n
также будет арифметической прогрессией с разностью 4). Поэтому T
”
n
=
.
Встреча автобусов в пункте А означает, что для некоторых натуральных n
и т
верно равенство
T
’
n
=
T
”
n
28
n
-34
m
=11
Левая часть этого уравнения — четное число, а правая — нет. Поэтому оно не имеет решений в целых числах. Следовательно, автобусы никогда не встретятся в пункте А.
Теперь перейдем непосредственно к решению второй части задачи. Для этого введем систему координат на дороге между А и В,
выбрав в качестве начала отсчета пункт А, в качестве положительного направления — направление от А к В (рис. 2).
Пусть x
1
(
t
),
x
2
(
t
)
— координаты первого и второго автобусов соответственно в момент t
.
Графики функций x
1
(
t
)
и x
2
(
t
)
— это ломаные линии, изображенные на рисунках 1 и 2 соответственно. Первая ломаная состоит из 102 пар звеньев с угловыми коэффициентами 51 и -51, а вторая — из 84 пар звеньев с угловыми коэффициентами 42 и -42 (на рисунках мы исказили масштаб). Точки А и В на оси ординат имеют координаты 0 и 2 соответственно и соответствуют прохождению через пункты А
и В.
Встреча автобусов в какой-то момент t
означает совпадение их координат в этот момент: x
1
(
t
) = x
2
(
t
),
то есть пересечение графиков функций x
1
(
t
)
и x
2
(
t
).
Каждое звено первой ломаной пересекает вторую ломаную ровно в одной точке. Поэтому всего будет 102 точки пересечения возрастающих звеньев первой ломаной со второй ломаной и 102 точки пересечения убывающих звеньев первой ломаной со второй ломаной. Поскольку автобусы не встречаются в пункте А, ни одна из этих точек не будет лежать на оси абсцисс. С другой стороны, поскольку автобусы встречаются 6 раз в пункте В, ровно 6 точек пересечения будет лежать на горизонтальной прямой у =
2. Эти точки будут включены как в 102 точки пересечения возрастающих звеньев первой ломаной со второй ломаной, так и в 102 точки пересечения убывающих звеньев первой ломаной со второй ломаной. Поэтому число точек пересечения, лежащих внутри
полосы 0 < у <
2, равно
2•(102-6)=192
Ответ:
а) 6 раз; б) 192 раза.