Диофантовы уравнения.
олимпиадные задания по алгебре (10 класс) по теме

Шехерезада рассказывает свои сказки великому правителю. Всего она должна рассказать 1001 сказку. Сколько ночей потребуется Шехерезаде, чтобы рассказать все свои сказки, если x ночей она будет рассказывать по 3 сказки, а остальные сказки по 5 за у ночей.

Решение.

Сказочнице, очевидно,  потребуется x+y ночей, где x и y  – натуральные корни диофантова уравнения 3х+5у=1001.

Решим это уравнение различными способами.

1. С помощью алгоритма Евклида

НОД(3,5)=1, уравнение имеет целые решения.

Получаем, что всего 67 целых значений переменной t содержится в указанном промежутке.

Например, при t= –335, получим  

у = -1001  +1005 =4; x =2002 – 1675 = 327, т. е. решение  (327; 4).

2. Способ с использованием цепной дроби.

Обратимся к уравнению 3х + 5у = 1001.

Решение.

1. Представим дробь 3/5  в виде конечной цепной дроби.

2. Запишем дробь в виде цепной дроби 3/5=[0;1, 1, 2]

3. Составим таблицу

4. Запишем общее решение уравнения:

Получили решение того же вида.  С учетом условия, что корни уравнения натуральные, имеем те же значения для переменной t, что и в первом случае. Так, при t= – 334  получается пара (332; 1).

Замечание. Можно усложнить задачу дополнительными вопросами.

1. Если бы Шехерезада хотела бы распределить свою 1001 сказку между как можно большим числом ночей, то какой вариант она должна выбрать?
2. Какой вариант позволит Шехерезаде сократить свой срок работы до минимума?

Требованию (1) удовлетворяет max (x +y) – наибольшая из сумм пар корней уравнения. Имеем x + у = 2002 +5t – 1001 – 3t= 1001+2t.

Очевидно,  max (x +y) достигается при t = –334. Итак, Шехерезада расскажет свои сказки самое большее за 333 ночи, если 332 ночи будет рассказывать по 3 сказки и только одну ночь – 5 сказок.

Ответу на второй вопрос соответствует вариант, когда t = –400, то есть решением уравнения будет пара (2; 199).  Шехерезада будет рассказывать 2 ночи по 3 сказки и 199 ночей по 5 сказок, тем самым,  сократив срок своей «работы» до 201 ночи.

3. Способ измельчения (рассеивания).

На занятии также можно рассмотреть решение данной задачи «методом измельчения». Обратимся к уравнению 3х + 5у = 1001.

Перепишем его иначе: x =   –  y +        и обозначим xl = у + x

        В результате уравнение примет вид  3х1 = 1001 – 2у  или

у =  –xl .

 Если вновь произвести замену у1 = у + х1, то придем к уравнению

x1 + 2у1 = 1001. Заметим, что коэффициенты при неизвестных уменьшились — измельчились.

 Здесь коэффициент при x1, равен 1, а поэтому при любом целом у1 = t число х1 тоже целое. Остается выразить исходные переменные через t:

 х1 = 1001 – 2 t,  следовательно, у = – 1001 + 3 t , а  x = 2002 – 5 t.  Итак, получаем бесконечную последовательность (2002 – 5 t , – 1001 + 3 t) целочисленных решений. Внешний вид формул для нахождения значений переменных отличается от решений, полученных ранее, но с учетом условия задачи, корни получаются те же самые.  Так, пара (332;1) получается при t = =334.