Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

ММ135

Конкурсная задача ММ135 (4 балла)

Конечно ли множество пар натуральных чисел (a,b), таких что остатки от деления a2 на b и b2 на a равны по 2011?

Решение

Положим: a1=3234, a2=8467, ai+1=3ai-ai-1. Легко проверяется и доказывается по индукции, что для любых трех соседних членов этой последовательности выполняется соотношение ai2=ai-1ai+1+2011, из которого следует, что любую пару соседних членов можно взять в качестве требуемых a и b.

Ответ: бесконечно.

Обсуждение

Существует много (возможно, бесконечно много) последовательностей, соседние члены которых будут подходящими парами. Например:

a1=2054, a2=18255, ai+1=9ai-ai-1;
a1=2090, a2=47979, ai+1=23ai-ai-1;
a1=2181, a2=10450, ai+1=5ai-ai-1;
a1=2545, a2=12194, ai+1=5ai-ai-1;
a1=3115, a2=40254, ai+1=13ai-ai-1;
a1=4298, a2=29459, ai+1=7ai-ai-1;
a1=4925, a2=12894, ai+1=3ai-ai-1.

Кроме того, существет много подходящих пар, в которых a и b не взаимно просты (разумеется, их НОД равняется 2011). Например, (4022, 6033) или (19*2011, 17285*2011). Но мне не удалось построить из таких пар какую-либо бесконечную серию.

Владислав Франк в качестве бесконечного множества подходящих пар использовал множество решений диофантова уравнения a2+b2-2011=37ab. А решение этого уравнеyия свел к решению обобщенного уравнения Пелля x2-1365y2=8044.

Разумеется, 2011 не является исключительным числом в смысле нашей задачи. Пусть m > 3. Положив a1=m2-3m+1, a2=m^3-5m2+6m-1, ai+1=(m-2)ai-ai-1, получим бесконечно много пар (соседних членов последовательности) таких, что остатки от деления ai2 на ai+1 и ai+12 на ai равны m. Сергей Половинкин заметил, что члены последней последовательности - это в точности значения чебышевских полиномов второго рода с четными номерами при x=√(m)/2.

При m < 4 указанный метод уже не приводит к возрастающей последовательности натуральных чисел и не дает подходящих пар. Однако, бесконечность подходящих пар для m=1 очевидна. Достаточно рассматривать пары соседних чисел. Более обще, если m=s2, то при a>m пара (a,a+s) будет подходящей.

Остаются два последних вопроса: Существуют ли подходящие пары для m = 2 и m = 3. И если существуют, то конечно ли их число? Ответ на первый вопрос положителен. Для m = 3 подходящими парами являются, например, (6, 33), (39, 69), (426, 753), (498, 19077), (789, 27066), (4647, 8214). Для m = 2 мне удалось подобрать всего одну пару (94, 1262). Таким образом, ответ на второй вопрос остается открытым.

Уже после опубликования этого разбора Дмитрий Пашуткин нашел бесконечные серии для случаев m = 3 и m = 2.

Для m = 3 годятся пары (ai, bi), где a1 = 69, b1 = 39,
ai+1 = 16ai - 9bi,
bi+1 = 9ai - 5bi. m = 3 и m = 2.

Для m = 2 годятся пары (ai, bi), где a1 = 1262, b1 = 92,
ai+1 = 10631719ai - 791904bi,
bi+1 = 791904ai - 58985bi.

Награды

К моему удивлению, с задачей ММ135 справились всего трое участников Марафона. За правилное решение и обобщение задачи ММ135 Сергей Половинкин получает 7 призовых баллов. Владислав Франк и Алексей Волошин получают по 4 призовых балла.

Дополнение: Дмитрий Пашуткин получает 4 призовых балла

Эстетическая оценка задачи ММ135 - 4.8 балла

Обзор задачи ММ135 подготовил Владимир Лецко


 

 


Страница: [[marathon:problem_135]]

marathon/problem_135.txt · Последние изменения: 2011/06/13 21:51 (внешнее изменение)
Powered by DokuWiki  ·  УКЦ ВГПУ 2006