«И возвращается ветер…», или периодичность в математике

«Идет ветер к югу, и переходит к северу, кружится, кружится на ходу своем, и возвращается ветер на круги свои.»              Екклезиаст, гл. 1, ст. 6

   Быть может, наибольшая привлекательность математики в том, что одни и те же идеи возникают при решении самых разнообразных задач, казалось бы не имеющих ничего общего.

В своей работе я  постараюсь проследить за одной из общематематических идей — идеей повторяемости, цикличности, возвращаемости.

Многие идеи, сформулированные в «чистом виде», выглядят избитыми, например принцип Дирихле. (Наиболее распостранённая  формулировка этого метода: Если кролики рассажены в клетки, причём число кроликов больше числа клеток, то хотя бы в одной из клеток находится более одного кролика.)  Но - удивительный факт - зачастую одно упоминание о такой «тривиальности» делает трудную до того задачу прозрачной. В чем здесь дело? Все встречали рисунки для детей, где надо найти, скажем, зайца в лесных зарослях. Мы хорошо знаем, как выглядит заяц, но где он сидит, сразу не видно. А если не сказать, что сидит именно заяц, то увидеть его очень трудно. Так и в математике полезно знать заранее, какие простые, но важные идеи скрываются в дебрях возможных рассуждений. В дальнейшем этот опыт будет подсказывать, какие «звери» могут водиться в том или ином лесу. А теперь вернемся «на круги свои».

Цикличность в природе встречается повсюду: карусели и вращение планет, времена года и цифры в десятичной записи дробей — практически все сущее участвует в каком-то циклическом движении, «хороводе». Оказывается, есть общая причина, вызывающая периодичность.

В детстве я, как впрочем и каждый из вас, складывал кубик Рубика. Эта головоломка привлекает внимание «всех групп населения» и получила широчайшее распространение.  Всем понятно, что при вращении граней некоторая комбинация выводит кубик Рубика из правильного положения. Но я заметил, что кубик можно снова собрать, повторив эту комбинацию еще несколько раз. Прошло время и я нашел объяснение этому, о чём поведаю далее. 

В чем секрет периодичности? Так же, как при изучении живой ткани рассматривают под микроскопом одну ее клетку, рассмотрим вначале простую «одноклеточную» задачу.

Задача 1. Найдите последнюю цифру числа 42012.

Давайте поставим более общий вопрос: как выглядит последовательность окончаний степеней четверки? Для начала выпишу несколько членов:           1, 4, 16, 64, 256, 1024, 4096,...

    В нечётной степени последняя цифра будет  4, если степень чётная, то последняя цифра будет 6 и почти очевидно, что так будет до бесконечности. Но все же почему? Да потому, что только последняя цифра каждой степени определяет последнюю цифру следующей степени, а остальные цифры не влияют, так что повторение одной цифры вызывает повторение следующей, а значит, и всех последующих.

Так возникает период — отрезок ряда между двумя повторениями. Теперь уже легко определить, что последняя цифра числа 42012 равна 6 .

   Следующая задача является уже «двуклеточной»: ее решение аналогично решению задачи 1, если суметь сначала доказать, что произойдет повторение. 

  Задача 2. Докажите, что последовательность остатков от деления на 2012 степеней числа 4-периодическая, причем длина периода не больше 2012.

   Всем хорошо известно, что рациональное число разлагается в периодическую десятичную дробь. Рассмотрю последовательность цифр этой периодической дроби. Как мы устанавливаем периодичность? При делении «уголком» мы работаем с последовательностью остатков (умножаем, вычитаем, берем остаток; сносим цифру, находим неполное частное, умножаем, вычитаем, берем остаток; и т. д.).  Вот начало этой последовательности: 1,4,16,64,256,1024,72,288,1152,584,324,1296… Итак, каждый остаток однозначно определяет неполное частное (цифру десятичной дроби) и следующий остаток.

   Остатки начнут повторяться,  значит, начнут повторяться и десятичные знаки. Остаток не может быть больше 2011. В моих исследованиях повторения начнутся при делении  4127 на 2012, то есть  4127= п·2012 + 4. Число остатков конечное. Очевидно, что  остаток может принимать значения от 0 до 2011, поэтому длина периода будет не больше 2012.

    Итак, периодичность десятичных знаков рационального числа получается как следствие периодичности соответствующих остатков. Теперь можно приступить к «многоклеточной» задаче.

  Задача 3. Жители Лавайских островов гордятся тем, что у них с незапамятных времен существует президентская форма правления. Каждые 4 года президентом избирается либо республиканец, либо демократ. Местные социологи обнаружили строгий закон, по которому определяется партийность очередного президента. Хотя этот закон засекречен, в печать просочились сведения, что партийность очередного президента полностью определяется партийностью предыдущих десяти. Последние три срока на Лаваях правит республиканец. Докажите, что всегда будут периоды правления трех республиканцев подряд.

   Достаточно показать, что партийности президентов периодически повторяются. Пусть «предвыборное состояние», или просто «состояние» это последовательность партий, к которым принадлежали последние 10 президентов. Каждое состояние определяет партийность следующего президента, а значит, и следующее предвыборное состояние. Состояний конечное число (не больше чем 2 10), следовательно, по принципу Дирихле, какое-то из них повторится. Повторение одного состояния вызовет повторение следующих состояний, и с этого момента «предвыборные состояния» начнут периодически повторяться, а значит, и  последовательность правящих партии будет периодической. Но поскольку президентская форма правления на Лаваях существует с незапамятных времен, повторение двух состояний уже произошло, и «предвыборные состояния» давно повторяются.

  Как видно, во всех разобранных задачах присутствует одно и то же рассуждение, устанавливающее периодичность. Сформулирую его в общем виде.

  Рассуждение 1. Если нечто может находиться только в конечном числе состояний, и состояние в данный момент времени однозначно определяет состояние в следующий момент времени, то, начиная с некоторого момента, состояния начнут периодически повторяться.

   Однако в задаче про президентов надо было проверить, что в данный момент мы находимся в периоде — только тогда можно утверждать, что всегда будут моменты правления трех республиканцев подряд. Для этого и потребовались «незапамятные времена». Это важный момент: рассуждение 1 утверждает периодичность, начиная с некоторого момента, но при этом вовсе не обязательно, чтобы повторилось первое состояние. (Это видно уже на примере задачи 1. Другой пример - периодические дроби.) Если период начинается не сразу, то последовательность состояний, предшествующая периоду, называется предпериодом. Чтобы доказать, что начальное состояние когда-нибудь встретится, надо еще показать отсутствие предпериода. Для этого часто используется несколько другая идея, чем в задаче о президентах, - идея «обратного хода»:

  Рассуждение 2. Если число состояний конечно, и каждое состояние

однозначно определяет как последующее состояние, так и предыдущее, то в последовательности состояний предпериод отсутствует.

   Это простое рассуждение не сразу становится понятным. Попробую его пояснить. С какого-то момента появится период (рассуждение 1). Выберем состояние, например, из третьего периода. Оно однозначно определяет предыдущее состояние и т. д. Во втором периоде есть такое же состояние; оно определяет предыдущее (такое же, как в третьем периоде) и т. д. Период «переносится в прошлое», а значит, все состояния периодически повторяются.

Задача 4. Докажите, что найдется член последовательности Фибоначчи, делящийся на 2012. (Последовательность Фибоначчи начинается с двух единиц, а каждый следующий член равен сумме двух предыдущих.)

Запишем формулу для определения очередного числа Фибоначчи:

ип =ип-1+ ип-2

Прежде всего изучу остатки чисел Фибоначчи при делении на 2012. Хотелось бы найти остаток, равный нулю. Ну, а как его искать? В том-то и задача. Обращусь к прошлому (задача о президентах показала полезность изучения истории). Замечаю, что последовательность можно «продолжить в прошлое» с помощью формулы: ип-2= ип - ип-1 Тогда получу, что и0=0. Прекрасно! Ноль делится на 2012.                                                    

   Осталось установить периодичность остатков, начиная с нулевого члена. Замечу: нам не нужно находить член последовательности Фибоначчи с нулевым остатком — достаточно установить его существование. Нетрудно понять, что по остатку одного числа Фибоначчи ничего нельзя сказать об остатке следующего. Тут на помощь приходит задача о президентах: ведь и там, чтобы спрогнозировать результат выборов, недостаточно знать партийность предыдущего президента — нужны результаты последних 10 выборов. Потому-то «предвыборным состоянием» мы назвали партийность последних 10 президентов. Теперь ясно, что в качестве состояния члена ип надо взять пару остатков от деления на 2012 членов ип-1 и ип-2.  Два предыдущих остатка уже определяют следующий. Здесь ключ к решению: во-первых, «состояние» определяет остаток числа, а во-вторых, каждое «состояние» определяет следующее состояние. Теперь все ясно: состояний конечное число , они начнут повторяться, а значит, повторятся остатки чисел Фибоначчи. Впрочем, радоваться рано. Почему период начинается с нулевого члена? Тут нам поможет идея «обратного хода»: состояние каждого остатка определяет состояние не только следующего, но и предыдущего (в этом нас убеждает формула ип-2= ип- ип-1), а отсюда отсутствие предпериода.

Идею цикличности можно формализовать не только на языке функций:

Теорема о периодичности. Пусть М — конечное множество (множество состояний). Пусть  f - функция из множества М в множество М. Тогда при всех х из М последовательность состояний  х,  f(x), f(f(x)), f(f(f(x))),… начиная с некоторого момента, станет периодичной.                                                                                                                            Кроме того, если при различных х и у состояния f(х) и f(у) также различны (это условие «обратного хода»! ), то период начинается с первого члена.            А теперь вернусь к кубику Рубика.                                                                               Задача 5. Некоторая комбинация поворотов граней вывела кубик Рубика из правильного положения. Докажите, что кубик можно снова собрать, повторив эту комбинацию еще несколько раз.                                                                Здесь подходит теорема о периодичности. Для решения этой задачи достаточно посмотреть на исходную комбинацию поворотов кубика как на функцию, переводящую одно его состояние в другое. Поскольку все повороты можно провести в обратном порядке, каждое состояние однозначно определяет предыдущее.  При этом разные состояния переходят в разные, после чего применяется теорема о периодичности.                                 Я применял некоторые приложения идеи цикличности, причем с «дискретным» случаем, когда число состояний конечно. Но и  «непрерывный»  случай, при бесконечном числе состояний, часто возникает периодичность или, вернее, «почти периодичность», когда состояния повторяются не абсолютно точно, а лишь приближенно. Поэтому, каждое лето и похоже, и непохоже на предыдущее.                                                                    Я закончу возвращением к Екклезиасту: «Восходит солнце, и заходит солнце, и спешит к месту своему, где оно восходит. Идет ветер к югу, и переходит к северу, кружится, кружится на ходу своем, и возвращается ветер на круги свои. Все реки текут в море, но море не переполняется; к тому месту, откуда реки текут, они возвращаются, чтобы опять течь... Что было, то и будет; и что делалось, то и будет делаться, и нет ничего нового под солнцем» (гл. 1, ст. 5—7, 9).