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

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

Занятие 18 (22 марта 2014 года). Циклы

1.

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

2.

На доске записано число 61. Каждую минуту число стирают с доски и записывают на это место произведение его цифр, увеличенное на 13. Какое число можно будет прочитать на доске через час?

(Например: после первой минуты на доске записано 19 = 6×1 + 13).

3.

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

4.

Начальник отдела, в котором служат 8 агентов, получил приказ об установлении взаимной слежки между агентами с номерами от 1 до 7 по схеме: первый следит за тем, кто следит за вторым, второй — за тем, кто следит за третьим, и т. д., последний следит за тем, кто следит за первым. Но в тот момент, когда начальник составил соответствующую схему, пришло дополнение к приказу — включить в эту группу и агента № 8. Сможет ли он теперь составить нужную схему слежки?

5.

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

6.

Древний египетский сейф открывается при помощи 100-значного кодового «слова», в котором все иероглифы разные. Археологам известны эти иероглифы, но не известен их порядок. Современный дешифровщик может переставлять местами два любых иероглифа из «слова». Докажите, что можно задать последовательность действий для такого дешифратора гарантировано открывающую сейф. Какова будет длина такой последовательности?

7.

Последовательность f(n) (n = 1,2,...), состоящая из натуральных чисел, такова, что f(f(n)) = f(n + 1) + f(n) для всех натуральных n. Докажите, что все члены этой последовательности различны.