Разрезания



Скачать 77.33 Kb.
Дата14.08.2018
Размер77.33 Kb.
#43780
ТипЗанятие

Математический кружок 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.

  1. Найдите остаток от деления 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.

  1. В последовательности 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.

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



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

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





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



  1. Разделите «в столбик» 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.

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

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

  1. На экране компьютера горит число, которое каждую минуту увеличивается на 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

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

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

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

  1. Цикл – это замкнутый путь по различным ребрам.
    Докажите, что если в графе нет циклов, то в нем есть хотя бы одна висячая вершина.

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

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

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


Скачать 77.33 Kb.

Поделитесь с Вашими друзьями:




База данных защищена авторским правом ©vossta.ru 2022
обратиться к администрации

    Главная страница