Как усложнить себе задачу: уравнения в целых числах

Когда мы только знакомились с понятием «уравнение», все было так просто: целые числа и коэффициенты, всего одна переменная – и она в равенстве встречалась только один раз! С тех пор в уравнения добавились степени и квадратные корни, специальные алгоритмы решения, дискриминанты, области допустимых значений и – страшно подумать! – вторая, третья переменная, а с ними пришли системы и дополнительные условия…

Но сегодня y нас для вас хорошие новости! На повестке дня особый тип задач – Диофантовы уравнения. За исключением наличия хотя бы двух переменных, они максимально просты – целые коэффициенты при каждой переменной и свободный член – ничего лишнего. Но в чем тогда подвох?

Казалось бы, одно уравнение и две переменные – достаточно выразить одну через другую и готово решение – не пара чисел, а полноценная прямая. Но древнегреческий ученый Диофант Александрийский ставил задачу немного иначе: целыми должны быть не только коэффициенты, но и значения переменных. Другими словами, Диофантовы уравнения решаются в целых числах, и их решениями может быть несколько (или бесконечное число) пар целых чисел.

Где мы можем столкнуться с Диофантовыми уравнениями? Например, при решении задач, где несколько искомых величин выражаются в штуках. В простейшем случае найти решения можно просто перебором. Приведем пример: из-под забора видно 18 ног, а за забором находятся только козы и страусы. Сколько и каких животных стоит за забором? Уравнение можно записать так: пусть y нас х коз и y страусов, тогда 4×х + 2×у = 18. Коз может быть не больше 4, так как в противном случае только их ног уже будет больше 18. Если коза одна, то страусов будет (18 – 4×1)/2 = 7, если козы две, то страусов 5, если 3 – то и страусов 3, если 4 – то страус один. Последний случай – коз нет вообще, тогда страусов 9. Мы перебрали все варианты.

Конечно, иногда коэффициенты уравнения гораздо больше, и простым перебором решать задачу мы будем очень долго. В этом случае на помощь приходит замечательное свойство целых чисел – делимость. Сразу разберем пример. Есть два типа контейнеров – по 130 и по 160 кг, при этом фургон может перевезти за раз 3 тонны груза. Сколько и каких контейнеров можно загрузить в фургон так, чтобы он был максимально нагружен?

Составляем уравнение и сокращаем всё, что сокращается:

130x+160y=3000

13x+16y=300

Заметим, что коэффициент при х – большое простое число 13. Можем попробовать вынести его за скобки. Вот что нам это даст:

13x+13y+3y=13×23+1

3y-1= 13×(23-x-y)

Так как правая часть делится на 13, то должна делиться и левая. Так как y не меньше нуля, перебор начинаем с него:

3y-1=0    y не целое

3y-1=13  y не целое

3y-1=26   y=9       x=12

3y-1=39  y не целое

3y-1=52   y не целое 

3y-1=65   y=22,  но 16×22=352>300

Получается, y задачи только одно решение: 12 контейнеров по 130 кг и 9 по 160 кг.

Что ж, y нас получилось уменьшить перебор в несколько раз, но что, если число решений задачи бесконечно? Как их искать, если даже перечислить эти пары чисел невозможно?

Никогда не забывайте: для математиков ничего невозможного нет! Для таких случаев существует особый универсальный метод решения – метод спуска!

Почему метод универсальный и куда нам с вами придется спускаться – лучше продемонстрировать на примере. Особая примета задач с бесконечным число решений – разные знаки коэффициентов при переменных, как в этом уравнении:

5x-7y=3

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

Полученное равенство справедливо для всех решений уравнения. Давайте предположим, что какое-то решение мы уже нашли. Тогда x и y – заведомо целые числа, а если левая часть равенства – целое, то и правая тоже. Однако мы с вами видим там сумму дроби с целым числом – и это означает, что дробь – тоже целое, числитель такой дроби делится на знаменатель нацело. Это дает нам возможность представить числитель как произведение какого-то (любого!) целого числа на 5 – согласитесь, тогда и только тогда оно поделится нацело. Обозначим это число за z – мы спустились до новых переменных:

2y+3=5z

Казалось бы, что поменялось? Мы просто заменили переменную x на переменную z? Это очень важный момент! В уравнении y нас была неизвестная переменная x, значение которой нужно было найти, а сейчас z – это возможность подставить любое целое число и получить равенство. Это не неизвестная, а произвольно задаваемый нами параметр – а значит, грубо говоря, известная величина.

Продолжаем наш спуск. Опять выразим переменную с меньшим коэффициентом – y:

Действуем по тому же плану: так как y и z – целые, то и z + 3 должно нацело делиться на 2, а значит, может быть выражено как целое число, умноженное на 2. Переходим к еще одному набору параметров – обозначим это целое число за t, тогда:

z +3=2t   z=2t-3

Вуаля! При любом целом t параметр z также будет целым – мы спустились до коэффициента, равного единице. Метод универсален именно потому, что при любых начальных коэффициентах мы рано или поздно дойдем до такого положения. Осталось только «подняться» вверх по цепочке преобразований, используя только последний ключевой параметр:

z=2t-3   y=3z-t=5t-9   x=y+z=7t-12

Мы выразили нужные нам переменные x и y через параметр t. Кажется, неизвестных букв стало еще больше? Нет, ведь как уже говорилось выше, вместо t мы можем взять любое целое число и получить верное равенство для таких значений x и y. А так как целых чисел бесконечное множество, то по найденным нами формулам можно получить бесконечное количество решений. Нам покорилась невозможная задача!