Периодичность и зацикливание

Пусть эта дробь является периодической и имеет какой-то предпериод длины и период длины После предпериода обязательно найдётся какая-то ненулевая цифра. Значит, период содержит ненулевые цифры. Однако, дробная часть содержит запись всех чисел вида Если взять достаточно большое то мы получим число, запись которого не входит в предпериод, и при этом его нули полностью покрывают один из периодов. Пришли к противоречию с наличием в периоде ненулевой цифры.

Предъявим такую последовательность. Будем чередовать блоки из чисел 1 и 2, каждый раз увеличивая количество единиц на одну:

Предположим противное. Пусть существует период длины Тогда найдётся момент, когда блок из единиц будет иметь длину, превышающую Поскольку после него идёт двойка, а затем снова блок из единиц, длина которого также больше мы можем выбрать такой блок бесконечно далеко, в том числе и за пределами предпериода. Пусть период частично попадает на начало этого блока, но из-за его длины весь следующий период будет состоять только из единиц. Однако период не может состоять только из единиц, так как в последовательности бесконечно много двоек. Получаем противоречие.

Из условия задачи понятно, что последовательность состоит из чисел не более чем четырёхзначных. Для удобства каждое значение будем записывать как четырёхзначное, например, 0041 или 0345. Очевидно, что каждое число однозначно определяет следующее, поэтому, если в последовательности повторится какое-то из них, то это будет означать, что появился цикл. Посчитаем, сколько всего может быть различных значений:

Таким образом, не позже чем через операций, число повторится. Следовательно, в последовательности обязательно есть период, длина которого не превышает

Пусть всего комнат. Рассмотрим -ое перемещение школьника к следующей двери. Пусть он подошёл к двери с номером Так как всего различных комнат комнату он точно посещал до этого. Запишем последовательность номеров комнат, между которыми перемещался школьник:

Так как последовательность комнат после однозначно определена, путь от до и будет искомым циклом.

Предположим обратное: пусть существует период длины Рассмотрим нашу последовательность. Понятно, что после 99 будут идти 10 десяток (с 100 до 109). После этого десятки будут появляться в последовательности после вычеркивания всех цифр, кроме первых двух, у значных чисел от до Такие блоки будут содержать десяток. Поскольку последовательность бесконечная, найдётся такое что Так как блоки, состоящие из более чем десяток, будут повторяться и дальше, то после предпериода найдётся период, который целиком попадёт в такой блок. Однако период не может состоять только из десяток, так как после них обязательно идёт число 11. Это приводит к противоречию. Следовательно, последовательность не может быть периодической.

Представим это как бесконечную последовательность состояний, где в состояние указывается: в какой замок или на какую развилку попал рыцарь, по какой из трёх дорог он туда пришёл и в какую сторону он должен повернуть. Таким образом если в королевстве замков и развилок, то состояний т.е. конечное число, при этом каждое следующие определяется по предыдущему. По принципу зацикливания такая последовательность рано или поздно зациклиться, а по принципу зацикливания назад предпериода не будет. Поэтому рано или поздно рыцарь вернётся к своему замку.

Так как у нас конечное число состояний, а так же каждое последующие определяется по конечному числу предыдущих, то можем применить принцип зацикливания. Согласно ему последовательность состояний погоды рано и поздно зациклиться, при чём в силу обратимости данной последовательности в ней не будет предпериода. Значит, раз одна “дождливая” неделя была, то такие недели всегда были и будут.

Пусть оказалось так, что для некоторого . Тогда выполнено . Действительно, на каждой следующей итерации мы учитываем только дробную часть исходного числа (целая же часть определяет только нашу “точку старта”). Поэтому выполнено равенство . Также отсюда будет следовать , то есть наш сдвиг по целой части будет таким же. Нетрудно видеть, что оба условия вместе дадут (если известно ). Далее остаётся только найти цикл нужной длины. Оказывается, что и выполнено , мы получили цикл, получаем

Замечание. Как же найти такой цикл, не считая вручную все значений до него? Во-первых, уже , что явно нам намекает, когда мы снова встретим единицу (по сути мы каждый раз умножаем дробную часть на 2, поэтому можно сразу сделать вывод, что на шаге, поскольку за столько же шагов результат возведётся в квадрат по модулю ). Во-вторых, уже на шестом шаге мы получим , поэтому далее можно попробовать идти по кратным шести индексам, чтобы быстрее добраться до . Почему вообще всё это имеет смысл? Потому что делится и на 6, и на 33, и на 66 — именно в них мы и ждём больше всего увидеть цикл, чтобы задача после этого решилась быстро и легко.

Легко вычислить: , поэтому

Следовательно,

Замечание.

Можно сразу вычислять значения функций в данной точке. Получится циклическая последовательность

Рассмотрим последовательности и Нетрудно видеть, что их сумма является периодической без предпериода.

Попробуем посчитать первые несколько членов, если встретятся две повторяющиеся пары соседних членов, мы победили, потому что каждый следующий член последовательности зависит от двух предыдущих. Первые члены имеют вид: Видим, что пара повторилась, следовательно, период равен

Рассмотрим последовательности и Нетрудно видеть, что как бы мы ни ставили и подряд, трёх одинаковых подряд идущих цифр мы не получим. Рассмотрим последовательность

Покажем, что она непериодична. Предположим противное, пусть она имеет период Рассмотрим её фрагмент, который состоит из и -шек, идущих за Пусть первая тройка у -ки имеет индекс тогда цифра с индексом также тройка, но под этим индексом стоит противоречие.

Предположим, что эта последовательность имеет период Обозначим сумму цифр числа n. Тогда при любом натуральном Разберём случаи.

Если сумма цифр нечётна и оно состоит из цифр, возьмём и сравнение не выполнится.

Если сумма цифр четная, посмотрим на первую цифру числа Если она чётная, возьмём и сравнение снова не выполнится. Если она нечётная, то можно взять

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

Предположим, что последовательность содержит предпериод. Обозначим его длину как Итак, для любого справедливо, что но (в противном случае не является частью предпериода). Рассмотрим следующую цепочку сравнения по модулю

Первое равенство выполнено по определению последовательности второе – поскольку и входят в периодическую часть последовательности; третье – поскольку четвертое – снова по определению последовательности

Посмотрим на третье и пятое выражение. Из них следует, что что противоречит нашему предположению. Значит, у последовательности предпериод отсутствует, и тогда С другой стороны, Левая часть и первое слагаемое правой части сравнимы с 1 по модулю значит второе слагаемое правой части, делится на Отсюда делится на а существование именно такого элемента нужно было найти по условию.

Вычислим еще несколько членов данной последовательности: , Так как при вычислении следующего члена мы используем только два предыдущих, а правило вычисления то же самое, то и так далее, то есть произошло зацикливание. Фрагмент будет раз за разом повторяться, и других чисел в данной последовательности не возникнет. Следовательно, значение зависит только от того, какое по счету место в такой шестерке этот член занимает. Для ответа на этот вопрос достаточно найти остаток от деления 100 на Этот остаток равен 4, значит, стоит на четвертом месте, то есть .

Рассмотрим двузначное число, образованное двумя последними цифрами. Среди двузначных чисел, кратных 23, нет числа, оканчивающегося на 1, а среди двузначных чисел, кратных 17, на 1 оканчивается только Следовательно, предпоследняя цифра — это Теперь рас- смотрим двузначное число, образованное третьей и второй цифрами с конца. На 23 оно делиться не может, а если оно делится на 17, то это Рассуждая аналогично, получим, что перед цифрой 8 может стоять только цифра 6, перед цифрой 6 — цифра 4 и так далее, причем каждая цифра восстанавливается однозначно.

Действуя таким образом, получим, что заданное число имеет вид …4692346851, причем выделенная группа из пяти цифр повторяется влево. Если отбросить три последние цифры, то число станет 2014 -значным. Так как остаток от деления 2014 на 5 равен 4, то искомая первая цифра числа — это четвертая с конца цифра в выделенной группе, то есть цифра

Выполнив деление числителя на знаменатель «в столбик», заметим, что последовательность цифр, стоящих после запятой, начиная с некоторого момента начнет повторяться, то есть будет периодической. Это принято записывать так: Значит, период получившейся дроби содержит цифр. Число при делении на дает остаток поэтому -я цифра после запятой в десятичной записи числа — это третья цифра периода, то есть цифра После ее зачеркивания на этом месте будет стоять цифра Следовательно, исходное число увеличилось.

Вычислим несколько первых членов этой последовательности: Так как число повторилось, то далее будут числа и то есть начиная с пятого числа образуется период Отбросим первые четыре числа, тогда число, стоящее на тысячном месте, станет -м. Так как делится на то искомое число равно

Обозначим данные числа через , Из условия задачи следует, что и Складывая эти равенства почленно, получим , то есть Аналогично из равенств и получим, что Тогда и так далее, то есть последовательность имеет период длины Следовательно,

Обозначим данные числа через По условию и Так как в заданном ряду нет нулей, то перемножив эти равенства почленно, получим то есть Аналогично из равенств и получим, что Таким образом, значит, последовательность периодична, а длина ее периода — Следовательно, тогда