Документ взят из кэша поисковой машины. Адрес оригинального документа : http://mmmf.msu.ru/archive/20052006/z9/?print
Дата изменения: Mon Oct 1 21:34:30 2012
Дата индексирования: Mon Oct 1 21:34:30 2012
Кодировка: Windows-1251
Зацикливание | 9 класс | Кружки | Малый мехмат МГУ

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

Руководители Иван Александрович Дорофеев и Степан Львович Кузнецов
2005/2006 учебный год

Листок 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 обладает следующим свойством: если x1x2, то f(x1) ≠ f(x2). Задана последовательность ak = f(ak − 1) (a2 = f(a1), a3 = f(a2), ...).
а)
Пусть последовательность ak зацикливается. Возможно ли, что f(an) = am при 1 < m < n?
б)
Пусть am = an (при m < n). Будет ли последовательность ak зацикливаться? Найдется ли такое s, что as = a1? Если да, то чему равно это s?