МАЛЫЙ МЕХМАТ МГУ

Кружок 9 класса

Листок 22. Зацикливание

1.

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

2.

Следующий член последовательности натуральных чисел равен последней цифре произведения двух предыдущих. Докажите, что последовательность а) периодична; б) с периодом длины не больше 26; в) меньше 17.

3.

В тридесятом королевстве у каждого зáмка и каждой развилки сходятся три дороги. Рыцарь выехал из своего замка и по очереди поворачивает то направо, то налево. Докажите, что его маршрут зациклится.

4.

Докажите, что если в задаче про одного преподавателя все записки указывают на разные кабинеты, то школьник рано или поздно вернётся в тот кабинет, с которого начал.

5.

Кубик Рубика выведен из первоначального состояния некоторой комбинацией поворотов. Докажите, что всегда можно вернуть его в первоначальное состояние, выполнив эту комбинацию ещё несколько раз.

6.

В последовательности 20068486... каждая цифра, начиная с пятой, равна последней цифре суммы четырёх предшествующих цифр. Верно ли, что в этой последовательности снова встретится четвёрка 2006?

7.

Верно ли, что в ряду Фибоначчи найдётся число, делящееся на 2006?

8.

Докажите, что найдутся две различные степени 2, разность которых делится а) на 1000; б) на 2006.

9.

Установлено, что погода на Сириусе в данный день полностью определяется предыдущей неделей. Варианты погоды: магнитная буря, метеоритный дождь, штиль. Последнюю неделю шёл метеоритный дождь. Докажите, что „дождливые” недели всегда были и будут.

10.

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

11.

Пусть p и q — натуральные числа, причём p не делится нацело на q и q имеет простые делители, отличные от 2 и 5. Докажите, что при делении p на q „в столбик”: а) не позднее, чем на q-м шаге мы получим то значение остатка, которое раньше уже появлялось; б) начиная с этого момента значения остатков и цифры частного будут повторяться периодически.

12.

Пусть функция f обладает следующим свойством: если x₁ ≠ x₂, то f(x₁) ≠ f(x₂). Задана последовательность a_k = f(a_{k − 1}) (a₂ = f(a₁), a₃ = f(a₂), ...).

а)

Пусть последовательность a_k зацикливается. Возможно ли, что f(a_n) = a_m при 1 < m < n?

б)

Пусть a_m = a_n (при m < n). Будет ли последовательность a_k зацикливаться? Найдётся ли такое s, что a_s = a₁? Если да, то чему равно это s?