Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/mccme/2009/7klass/29r.doc Дата изменения: Sat Apr 25 21:21:50 2009 Дата индексирования: Sat Oct 17 02:26:36 2009 Кодировка: koi8-r

Математический кружок 7 класс
Занятие ?29 Зацикливание. 18.04.08

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

Ответ. 4

Решение. Вычислив первые 10 последних цифр, заметим, что последние цифры
зацикливаются: (2, 4, 8, 6), (2, 4, 8, 6), .

Эта закономерность будет продолжаться и дальше: в самом деле, каждая
следующая цифра получается из предыдущей умножением на 2 (смотрим
только на последнюю цифру результата), поэтому после 2 всегда будет идти
4, после 4 всегда будет 8, послед 8 всегда 6, а после 6 - снова 2. В
цикле всего 4 числа, поэтому 248 заканчивается на 6 (12 полных циклов),
249 - заканчивается на 2, а 250 - заканчивается на 4.

2. Найдите остаток от деления 3100 на 7.

Ответ. 4

Решение. По прошлому занятию мы знаем, что для того чтобы узнать остаток
произведения надо перемножить остатки сомножителей. То есть если число
3n дает при делении на 7 остаток r, то число 3n+1 дает такой же остаток,
как число и 3r.

Посмотрим на остатки нескольких первых степеней тройки (начиная с 31):
3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5, . Видно, что остатки зацикливаются. Эта
закономерность будет и дальше,- всегда после 3 будет идти остаток от
3(3=9, то есть 2; после 2 остаток 2(3=6; после 6 остаток от 6(3=18, то
есть 4; после 4 остаток от 4(3=12, то есть 5; после 5 остаток от 5(3=15,
то есть 1; после 1 будет идти остаток 1(3=3.

В цикле всего 6 остатков (3,2,6,4,5,1), значит, 396 будет давать остаток
1, а 3100 будет давать остаток 4.

3. В последовательности 1, 1, 2, . два первых числа равны 1, а каждый
следующий равен произведению двух предыдущих, увеличенному на единицу:
an + 1 = an . an - 1 + 1. Докажите, что число a444 не делится на 4.

Решение. Посмотрим, какие остатки дают числа последовательности при
делении на 4. Первые три числа - 1,1,2, а далее каждый следующий
определяются по предыдущим двум остаткам. Получается 1, 1, 2, 3, 3, 2,
3, 3, 2, 3, 3. Кто дочитал до этого места - попросите у нас на следующем
занятии конфету, число конфет - ограничено. Вообще всегда после 2 и 3
будет идти остаток 3, а после 3 и 3 будет идти остаток 2. Значит
последовательность 2, 3, 3, будет циклически повторяться. Таким образом,
в последовательности не встретится нуля, а, значит, не будет чисел
делящихся на 4.

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

[pic]

Ответ. Да, Петину таблицу можно восстановить.

Решение. Пусть во второй и третьих клетках стоят числа x и y,
6+x+y = 15. Так как сумма любых трех последовательно идущих чисел равна
15, то четвертое число должно быть равно 6, т.к. 15-x-y=6. Аналогично
пятое число - x, шестое - y, и т.д.
[pic]
[pic]

Итак, мы добрались до числа 4, на месте которого по нашему предположению
должно стоять число y, значит y = 4, тогда x = 15-6-4 = 5. Таким образом
Петина таблица имеет следующий вид:

[pic]

5. Разделите «в столбик» 3 на 14. Какая цифра будет стоять после запятой на
100 месте?

Ответ. 2.

Решение. Будем делить до тех пор, пока не повторится остаток,
встречавшийся ранее:

3, |0 | |1 |4 | | | | | | | |2 |8 | |0, |2 |1 |4 |2 |8 |5 |7 | | |2 |0 |
| | | | | | | | | |1 |4 | | | | | | | | | | | |6 |0 | | | | | | | | | |
|5 |6 | | | | | | | | | | | |4 |0 | | | | | | | | | | |2 |8 | | | | | |
| | | | |1 |2 |0 | | | | | | | | | |1 |1 |2 | | | | | | | | | | | |8 |0
| | | | | | | | | | |7 |0 | | | | | | | | | | |1 |0 |0 | | | | | | | | |
| |9 |8 | | | | | | | | | | | |2 |0 | | | | | | | | | | | | | | | |-
заметим, что у нас повторился остаток 2, т.е. мы, как и раньше, будем
делить 20 на 14, как и раньше, возьмем 1, остаток получится 6 и снова,
как раньше, будем делить 60, т.е., начиная с этого места, в частном
будет повторяться последовательность цифр 142857.

Заметим теперь, что самая первая цифра после запятой (двойка) не входит
в этот цикл. Кроме нее у нас осталось 99 цифр после запятой - в них
входит 16 полных циклов по 6 цифр и еще три цифры, т.е. наша искомая
цифра будет третьей в цикле, т.е. это 2.

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

Решение. Кабинетов всего конечное число, поэтому рано или поздно
школьник придет к тому кабинету, у которого он уже был. Пусть это было
так - школьник сначала прошел n различных кабинетов, а после n-го по
счету кабинета попал в кабинет, в котором уже был, скажем ,k-й по счету
(k далее до n-го, из n-го он снова пойдет в k-й и так далее. То есть,
школьник так и будет все время ходить по циклу от k-го кабинета до n-го.

7. На экране компьютера горит число, которое каждую минуту увеличивается на
102. Начальное значение числа 123. Программист Саша имеет возможность в
любой момент изменять порядок цифр числа, находящегося на экране. Может
ли он добиться того, чтобы число никогда не стало четырёхзначным?

Ответ: да.

Решение 1. Саша может действовать следующим образом. Сначала подождать,
пока последняя цифра станет 1 или 2. Это случится не более чем через 5
минут независимо от того, какая последняя цифра сейчас. После этого
поменять местами эту цифру с первой. Первая цифра стала 1 или 2, за
следующие 5 минут она может увеличиться не более чем на 6, т.е. число
останется трехзначным. Как только третья цифра стала 1 или 2, он снова
ее меняет с первой. И т.д.

Решение 2. Приведем другую стратегию действий для Саши.

123-> 225 -> 327-> 429-> 531-> 135->237->327.

У нас повторилось число 327, значит, дальше мы сможет менять числа по
циклу 327-> 429-> 531-> 135->237->327

8. Вершина графа называется «висячей», если из нее выходит только одно
ребро.

Нарисуйте граф с 10 вершинами, в котором висячих вершин нет, но есть
такая вершина, что если стереть её и все выходящие из неё рёбра, то в
оставшемся графе будет ровно 5 висячих вершин.

Решение. Есть очень много разных вариантов, один из примеров приведен на
рисунке.

Замечание. Граф не обязательно должен быть связным.

9. Цикл - это замкнутый путь по различным ребрам.

Докажите, что если в графе нет циклов, то в нем есть хотя бы одна
висячая вершина.

Решение. Предположим, что в графе нет циклов и нет висячих вершин.

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

Замечание. Можно доказать, что если в графе нет циклов, то в нем есть
хотя бы две висячие вершины.

-----------------------
[pic]

15

15

15