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


Содержание

ММ164

Конкурсная задача ММ164 (РК-4) (6 баллов)

По мотивам задачи ММ135

В задаче ММ135 приведено несколько рекуррентных последовательной вида ai+1=dai-ai-1 соседние члены которых дают бесконечные множества пар натуральных чисел (a,b) таких, что остатки от деления a2 на b и b2 на a равны 2011. Существует ли натуральное число c<2000000, для которого найдется не менее 100 последовательностей с попарно различными d, соседние члены которых дают бесконечные множества пар натуральных чисел (a,b) таких, что остатки от деления a2 на b и b2 на a равны c?

Решение

Пусть c=ef+1, где натуральные e и f удовлетворяют условию e+2<f. Положим d=f-e, a0=1, a1=f, ai+1=dai-ai-1. Легко проверяется, что для членов этой возрастающей последовательности выполняется соотношение ai2-ai-1ai+1=c. Поэтому, любые два соседних члена, больших c, дают подходящую пару. Остается найти c<2000000 такое, что с-1 будет иметь достаточно делителей. Таким будет, например, число c=665281=26⋅33⋅5⋅7+1. Поскольку \tau(c-1)=224, для него найдется более 100 подходящих d.

Обсуждение

Существует совершенно тривиальное решение задачи ММ164. Достаточно взять c=r2. Тогда при любом d>2 последовательность, начинающаяся с a0=r, a1=dr, будет подходящей. Поэтому при составлении и решении задач ММ135 и ММ164 я сосредоточился на рассмотрении c, не являющихся полными квадратами. И настолько свыкся с этим. что забыл упомянуть в условии, что c не должно быть квадратом. К чести марафонцев все они сумели прочитать мысли ведущего и искали c, отличные от квадратов.

Предлагая эту задачу, я видел, что диофантово уравнение x2-dxy+y2=c (1), к решению которого сводится отыскание интересующих нас последовательностей, разрешимо не только при d, описанных выше. Конечно, я попытался найти закономерность, которой бы подчинялись все d, для которых (1) разрешимо. Но тщетно. Значительное продвижение в этом направлении (а точнее, обобщение предыдущего рассуждения) сделал Олег Полубасов:

Пусть c=r2(ef+1), e+2<f. Положим d=f-e, a0=r, a1=rf, ai+1=dai-ai-1. И мы вновь получили требуемую последовательность.

Но задача оказалась коварной. Существуют разрешимые уравнения вида (1) (а значит, и искомые последовательности), для которых d b c не связаны описанным способом. Вот пример, найденный Олегом Полубасовым: При c=170244, d=4862 уравнение (1) разрешимо, но это d нельзя получить вышеописанным способом.

Приведу еще несколько интересных фактов, найденных (Вы уже, конечно, догадались!) Олегом Полубасовым.

Случаи c=2 и c=3 единственные (если, конечно, два числа могут единственными) натуральные числа, для которых не существует подходящих последовательностей. Это, разумеется, не отменяет дополнения к ММ135, найденного Дмитрием Пашуткиным. Существует бесконечно много пар натуральных чисел таких, что остаток от деления квадрата каждого из них на другое число пары равен 3. Ситуация для двойки аналогична. Но эти пары не являются решениями уравнения (1) ни при каких d и рекуррентные соотношения для таких пар более сложны.

Наименьшее c, удовлетворяющее условию задачи равно 33049.

Существует аж 51069 натуральных чисел, не превосходящих 2000000 и не являющихся квадратами, для каждого из которых найдется не менее 100 подходящих d. Для 161-го из этих чисел требуемое количество d можно получить, основываясь только на разложениях c-1.

Наибольшее количество последовательностей (а именно, 303) с попарно различными d порождает число 1995841 = 1 + 2^6*3^4*5*7*11. Вот список d: 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 21, 22, 23, 24, 25, 26, 28, 30, 34, 37, 38, 40, 42, 43, 44, 46, 47, 54, 57, 58, 61, 67, 68, 74, 77, 78, 79, 82, 86, 93, 94, 99, 102, 103, 106, 112, 141, 142, 145, 152, 154, 163, 166, 179, 180, 192, 194, 195, 200, 226, 244, 248, 249, 251, 252, 258, 262, 268, 306, 324, 332, 344, 348, 362, 366, 382, 383, 388, 394, 397, 418, 443, 453, 492, 493, 504, 545, 548, 572, 573, 574, 579, 583, 626, 646, 662, 666, 670, 724, 768, 824, 834, 838, 871, 889, 934, 972, 982, 1006, 1010, 1023, 1026, 1033, 1043, 1119, 1146, 1150, 1167, 1236, 1248, 1349, 1360, 1388, 1402, 1442, 1446, 1454, 1501, 1536, 1582, 1594, 1654, 1725, 1728, 1802, 1822, 1884, 1888, 1898, 1993, 2006, 2026, 2052, 2131, 2187, 2251, 2298, 2364, 2372, 2432, 2510, 2538, 2598, 2624, 2638, 2737, 2763, 2766, 2889, 2953, 3004, 3148, 3156, 3252, 3456, 3537, 3678, 3858, 3952, 4007, 4096, 4188, 4310, 4318, 4332, 4523, 4644, 4750, 4799, 4902, 5184, 5318, 5584, 5604, 5718, 5836, 5917, 5933, 6021, 6172, 6423, 6634, 6642, 6848, 7122, 7214, 7296, 7660, 7668, 8076, 8314, 8409, 8526, 8686, 8852, 9024, 9294, 9498, 9502, 9882, 10203, 10371, 10502, 10908, 11164, 11669, 11712, 11877, 11931, 12158, 12314, 12784, 12806, 13716, 14116, 14649, 14988, 15118, 15714, 16512, 16627, 17708, 18034, 18142, 18372, 18903, 19952, 20061, 20694, 21688, 22086, 22174, 22592, 23676, 24559, 24868, 25843, 27648, 27718, 28442, 30174, 31121, 31617, 33204, 33260, 35584, 35638, 36233, 36906, 38378, 41532, 44307, 45316, 47478, 47518, 49856, 55404, 56989, 60447, 62338, 66498, 66526, 71252, 73893, 83136, 83157, 90698, 95019, 99772, 99790, 110862, 124724, 133041, 142546, 166308, 166318, 181429, 199574, 221751, 249472, 285113, 332634, 332638, 399163, 498956, 665277, 997918, 1995839.

Число c = 2011, рассмотренное в задаче ММ135, порождает 23 последовательности с попарно различными d. Список d: 3, 5, 7, 9, 11, 13, 17, 23, 37, 43, 47, 57, 65, 93, 107, 119, 191, 329, 333, 397, 667, 1003, 2009.

Познакомится с решением Олега можно :здесь

Награды

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

Эстетическая оценка - 4.9 балла


 

 


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

marathon/problem_164.txt · Последние изменения: 2012/10/06 14:31 (внешнее изменение)
Powered by DokuWiki  ·  УКЦ ВГПУ 2006