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


Содержание

ММ45-46

Конкурсная задача ММ45-46 (30 баллов)

Функция f(n) задается так: Натуральные числа от 1 до n расставлены по кругу. Начинаем отмечать числа 1, 2, 4, 7, 11, 16 и т.д. Значением f(n) будет то число, которое первым будет отмечено повторно.

45.1) Доказать, что существует бесконечно много n, для которых f(n) = 500501. (5 баллов)
46.1) Найти явную формулу для f(3k). (4 балла)
46.2) Описать все такие n, для которых f(n) определяется на n+1-вом шаге, (т. е. все числа будут отмечены по разу, прежде чем какое-то будет отмечено повторно). Найти явное выражение f(n) для таких n. (4 балла)
46.3) Доказать, что на множестве нечетных простых чисел f(n) инъективна (т.е. f(p) не может равняться f(q), если p и q - различные нечетные простые числа). (7 баллов)
45.2) Верно ли, что для любого натурального m найдется n такое, что f(n) = m?
45.3) Верно ли, что существует бесконечно много таких n, для которых f(n) = n?

Решение

Числа 1, 2, 4, 7, 11, 16, естественным образом возникающие в этой задаче, я буду называть «посттреугольными» (поскольку каждое из них следует за соответствующим треугольным числом). Общая формула посттреугольных чисел - (k+1)k/2 + 1.

45.1.

Число 500501 является посттреугольным.
Докажем, что все посттреугольные числа встречаются в последовательности f(n) бесконечное число раз.
Пусть m - посттреугольное число. Тогда при n = t - m, где t - посттреугольное число, большее (m2 - m + 2)/2, f(n) будет равно m. В самом деле, m (как и любое посттреугольное число, меньшее n) будет отмечено на первом круге. Оно же будет первым отмечено на втором круге.

Прежде чем рассматривать остальные пункты, докажем, что если m (равное f(n)) первый раз отмечается на k-том круге, повторно оно будет отмечено уже на следующем, k+1-вом круге.

Приведу доказательство этого факта, предложенное Андреем Винокуровым.

Пусть f(n) отмечается первый раз на i+1-вом шаге и на k-том круге, а второй раз - на j+1-вом шаге и на t-том круге.
Тогда f(n) = i(i+1)/2 + 1 - (k-1)n = j(j+1)/2 + 1 - (t-1)n.
Отсюда (j-i)(j+j+1) = 2(t-k)n. (1)
Надо доказать, что t-k = 1.
Соотношение (1) показывает, что 2(t-k)n = ab, где a и b - натуральные числа различной четности, и что пара натуральных чисел (j,i) является решением системы {x-y = a, x+y+1 = b}.
Очевидно, что эта система разрешима в натуральных числах всякий раз, когда b больше a и натуральные числа a и b имеют разную четность.
Допустим, что t-k > 1. Тогда у t-k имеется простой делитель p. Тогда 2(t-k)n/p = ab/p. Значит, на p делится, по крайней мере, одно из чисел a, b. Поделим его на p и обозначим через a' меньшее из получившихся чисел (a' может оказаться равным a/p, a или b/p), а через b' - большее (соответственно b' будет равно одному из чисел b, b/p или a). Отметим, что a' и b' по-прежнему будут разной четности (оба они не могут стать нечетными из-за множителя 2 в (1)). Значит, система {x-y = a', x+y+1 = b'} разрешима в натуральных числах. Пусть (j',i') - ее решение. Тогда j' = (a'+b'-1)/2 < (a+b-1)/2 = j. Следовательно, значение f(n) определится раньше, чем на j-том шаге, что противоречит выбору j.

Теперь понятно, что значение f(n) определяется так:
Пусть 2n = ab - представление числа 2n в виде двух сомножителей разной четности такое, что a меньше b и разность b-a минимальна (Андрей Винокуров предложил называть такое представление «определяющим разбиением»).
Тогда f(n) = (x2 + x)/2 mod n + 1, где x = (a+b-1)/2 (тот же результат получится и при x = (b-a-1)/2 ).

46.1

Пусть n = 32k.
Тогда определяющее разбиение - 2n = ab, где a = 3k, b = 2*3k и f(n) = [(3k - 1)/2 * (3k + 1)/2]/2 + 1 = (32k + 7)/8.
Пусть теперь n = 32k+1. Тогда определяющее разбиение - 2n = ab, где a = 2*3k, b = 3k+1k. Учитывая, что 3k+1 - 2*3k = 3k, получаем, что и в этом случае f(n) = (32k + 7)/8.
Весьма любопытна и рекуррентная формула для f(3k):
f(3) = 1, f(32k) = f(32k-1) + 32k-2, f(32k+1) = f(32k).

46.2

Для того, чтобы f(n) определялось на n+1-вом шаге, необходимо и достаточно, чтобы j+1 = (a+b-1)/2 = n+1, т.е. 2n = a+b-1. Но 2n = ab. Поэтому a+b = ab+1. Такое равенство возможно (в натуральных числах с a меньшим b) только при a = 1. Т.е. определяющее разбиение 2n = 1*2n, это равносильно тому, что n - степень двойки. f(2k) = (2k - 1)*2k/2 mod 2k + 1 = 2k-1 + 1.

46.3

Пусть n - простое нечетное.
Определяющее разбиение для таких n - 2n = 2*n.
f(n) = (n-3)(n-1)/8 mod n + 1 = 3/8 mod n + 1
При n = 8k + 1 это соотношение дает f(n) = (5n+11)/8;
при n = 8k + 3 f(n) = (7n+11)/8 (за исключением k=0, для которого f(3) = 1);
при n = 8k + 5 f(n) = (n+11)/8;
при n = 8k + 7 f(n) = (3n+11)/8;
Если допустить, что f(p) = f(q) при различных p и q, получим:
(tp+11)/8 = (sq+11)/8, где s и t берутся из множества {1,3,5,7}.
Последнее равенство равносильно соотношению tp=sq, которое очевидно невозможно, когда хотя бы одно из (простых) чисел p и q больше 8. В том, что f(p) не может равняться f(q) при малых p и q, легко убедиться перебором.

Обсуждение

На задачи 45 и 46 я получил рекордное количество ответов (при том, что количество отвечавших было совсем не рекордным).
Очень пестрым выглядит и разброс эстетических оценок задач: от единиц до пятерок с плюсом. Но тот факт, что некоторые участники прислали по пять, шесть и больше писем на одну и ту же тему, красноречивее их оценок указывает, что задачка пришлась им по душе.
Особенно «зацепили» марафонцев пункты 45.2 и 45.3. Но время подробного разговора о них еще не пришло.

Легко видеть, что посттреугольное число m может быть значением f(n) и при n, меньших, чем указано в решении 45.1. Однако, для n, бОльших порогового значения (m2 - m + 2)/2, посттреугольные числа встречаются в качестве значений f(n) только для чисел, указанных в решении.

По аналогии с пунктом 46.1 легко вывести формулы для нахождения нахождения f(5k), f(7k), f(11k) (правда, в этом случае значения f(p2k+1) уже не будут повторять значения f(p2k)). Начиная с p = 13, ситуация будет несколько сложнее, т.к. значение f(pk) перестанет определяться для нечетных k уже на втором круге. Однако для четных степеней нечетных простых чисел существует (найденная Олегом Полубасовым) простая формула f(n) = (n+7)/8.

Маша Никулина высказала гипотезу, что f(n) сюръективна уже на множестве простых n. К сожалению (для пункта 45.2), это не так. Наименьшее число, не представимое в виде f(n) ни при каком простом n - 7. А вообще таких чисел довольно много. В частности, значениями f(n) для простых нечетных n не могут быть посттреугольные числа, бОльшие 11 (еще одна несложная задачка про f(n)).

45.2

Я думаю, что ответ на вопрос этого пункта положителен. Однако доказать гипотезу о сюръективности f(n) пока не удалось ни мне, ни кому-либо из участников марафона.

Косвенным подтверждением справедливости гипотезы может служить тот факт, что для каждого конкретного m, как правило, без труда удается найти прообраз. Так, для чисел из первой тысячи я (пока) не смог найти прообраз только для m = 917.
Вот перечень чисел из первой тысячи, для которых известные мне наименьшие прообразы превышают миллиард:
209 = f(161 803 409 657);
224 = f(2 234 954 282);
588 = f(10 540 433 474 488);
705 = f(868 109 938 408);
770 = f(1 029 467 912);
788 = f(2 176 329 914);
867 = f(67 257 364 837);
914 = f(3 037 524 523);
929 = f(2 826 599 040 574).
Причем большинство приведенных прообразов гарантированно абсолютно наименьшие для данных m.
В том, что прообразы относительно небольших чисел бывают столь велики, нет ничего удивительного, если учесть, что при их отыскании сплошь и рядом возникает (обобщенноее) уравнение Пелля, для решений которого такие всплески весьма характерны.

45.3

Андpей Винокуpов доказал (я не привожу здесь это доказательство из-за гpомоздкости), что числа n, для котоpых f(n) = n, обязаны быть посттpеугольными. Таким обpазом, искомые n должны отмечаться повтоpно уже на втоpом кpуге. (Любопытно, что и дpугие маpафонцы, ломавшие голову над 45.3, искали подходящие числа именно сpеди посттpеугольных).
То, что сpеди постpеугольных чисел существует бесконечно много таких, котоpые будут повтоpно отмечаться на втоpом кpуге, удалось доказать сpазу нескольким участникам маpафона.
Этот факт следует из бесконечности числа pешений обобщенного уpавнения Пелля x2 - 2y2 = 7. (*)
Это уpавнение давно и хоpошо изучено (Андpей Винокуpов, подозpевая, что «изобpетает велосипед», пеpеpешил его самостоятельно).
Hатуpальные pешения (*) описываются фоpмулами:
(3+s)(3+2s)n и (5+3s)(3+2s)n, где s = sqrt(2), а n - целое неотpицательное. Это же решение может быть представлено в виде объединения двух пар рекуррентных последовательностей:
1) x[1] = 3, y[1] = 1, x[i+1] = 3x[i] + 4y[i], y[i+1] = 2x[i] + 3y[i];
2) x[1] = 5, y[1] = 3, x[i+1] = 3x[i] + 4y[i], y[i+1] = 2x[i] + 3y[i];

Пусть (x,y) - pешение (*). Тогда n = (y2-1)/8 + 1 будет отмечаться на пеpвом и втоpом кpугах.
Беда в том, что не всякое pешение (*) пpиводит к нахождению n, для котоpого f(n) = n. Может оказаться, что какое-то дpугое посттpеугольное число, меньшее n, тоже будет отмечено на втоpом кpуге.

Андpей Винокуpов ввел в pассмотpение еще две последовательности (вновь задаваемые одним и тем же pекуppентным соотношением, но pазными начальными условиями), позволяющие поpождать посттpеугольные числа, отмечаемые на втоpом кpуге:
p[1] = 1, p[2] = 2, p[i+1] = 6p[i] - p[i-1]; (* *)
q[1] = 1, q[2] = 4, q[i+1] = 6q[i] - q[i-1]. (* * *)

Числа n[i] = p[i+1]p[i]/2 и n'[i] = q[i+1]q[i]/2 - это, в точности те n, котоpые нас интеpесуют.

Вот перечень наименьших n, для которых f(n) = n:
1, 2, 11, 46, 352, 11936, 177556, 13773377, 69683724541, 18342198104231, 164575146945554972599627147231, 7445227251230831738604281205366013502, 66573397926910596289557051696571177832516.

Легко видеть, что если p[i] (или q[i]) - пpостое, то поpожденное им n удолветвоpяет тpебуемому соотношению f(n) = n, поскольку в этом случае pазбиение 2p = p[i](p[i-1]/2) является опpеделяющим.

Использование этого обстоятельства позволяет найти еще ряд монстров, для которых f(n) = n.
Например, n =
189101560269717676782278014401678699129321943473707022024163473572148034593088453115310037837081159773403 19540183280085576668355674321728706747896839126911456327229380180246844495684748358291227471202038894036796039110001720 58207076127756004716009091425415302154650098924340626136278824871018748753077482075644729886234503426874101995218746399 59566755877812617980213779111969625823456911499698473059042457980040055868337952766790855023601728472473894834974403606 60952053147061487987240626261998674518229239677007299521028779693792722131880113880674987490842960253594347237873520183 13669050665798304615900609578276825212207595082925081332096977379156937532686750551584432433161639593162571153554934853 89757799232378935355860743064390907590521831626323236943070500848231797793875261076483395732364953462494802904139185020 37888757108339190423053312704967423432129779187507490197720914439796533548893846174194624921601072790909853081190070468 75720420333413518661296941521597397387528355726615712342373468713681332156832053050546829357241505869617062829497657934 55893684259294463636331214450551205939534535647694956444252918801151147890302692316372488604551893529192804636356475002 01843749304729196390157642364370427831085014518555824320671910506897555210559362277081556059292568834235321258078938256 54633834352524780377972093598199808898572587882680941523739705628145729091922783610477669745211540678341554248311337367 74878921243411861550084748724015423682583796426397844890158215256342960765596052129279526051829037453522880802808694061 57352493783824140294128271932012324244314071840201847732302586906348923436109555424304295726119117674070892926263457807 72003969564354963024041502327137369577603505369962036303490456991109271664325448021016743574746720845187516404672077882 70665550864934500203985255682790154941244375763265347151168454639614716974370922744027908914584870832522960510814305546 3744547959941925444117499753616215909372751904564524604194673047497716622217310469273351922064090805357095365691

К сожалению, доказывать, что в последовательностях (* *) и (* * *) бесконечно много простых чисел я не умею.
Таким образом, на сегодняшний день окончательного ответа на вопрос пункта 45.3 нет, хотя то, что этот ответ положителен представляется очень правдоподобным.

Уже после того, как был опубликован приведенный выше разбор, Рустем Айдагулов (Руст) прислал свое решение MM45-46
Легко видеть, что его решение (с допущением о бесконечности множества простых значений соответствующего многочлена) практически совпадает с приведенным в обсуждении.
Вопреки высказанному выше предположению Рустем утверждает, что f(n) не сюрьективно, т.е. ответ к пункту 45.2 отрицательный. Но обоснование этого утверждения, мягко говоря, не достаточно развернуто.

Награды

Ряд марафонцев не согласны с распределением баллов по пунктам задачи, считая, что объективно самый легкий пункт 45.1 несправедливо стоит дороже, чем более содержательные 46.1 и 46.2.
В свое оправдание могу заметить, что 45.1 был опубликован намного раньше. К тому моменту, когда появилась задача 46, участники, основательно поломавшие головы над 45.2 и 45.3, «щелкали» вопросы задачи 46 без особых затруднений.

За верное решение задачи ММ46 Андрей Богданов, Андрей Винокуров, Владислав Франк, Олег Полубасов и Макс Алексеев получают по 20 призовых баллов.
Маша Никулина получает 8 призовых баллов. Она решила ММ45.1, дала верный, но не полностью обоснованный ответ к ММ46.2, привела ряд соображений по ММ46.3 (ее решение в любом случае не следует приведенному здесь).
Константин Кноп и Владимир Марунин получают по 5 призовых баллов за верное решение ММ45.1.
Валентина Загороднюк получает 1 призовой балл за указание рекуррентной (а не явной и без обоснований) формулы в ММ45.1.

За pазумные шаги в напpавлении pешения 45.2 и 45.3 Константин Кноп, Олег Полубасов и Макс Алексеев получают по 6 пpизовых баллов, а Андpей Винокуpов - 10 пpизовых баллов.

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


 

 


Страница: [[marathon:problem_mm45-46]]

marathon/problem_mm45-46.txt · Последние изменения: 2017/12/21 13:37 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006