Задача по математике на тему: «Зацикливание и периодичность»

Предыдущая упражнение. (решенное)
Задача. Первое число последовательности — натуральное число, меньшее 10 000. Каждое следующее число в последовательности получается из предыдущего так: число возводится в квадрат и от него оставляется число, образованное последними четырьмя цифрами. Докажите, что последовательность периодическая (возможно, с предпериодом) и сделайте какую-нибудь оценку длины периода.
Решение. Рассмотрим граф, в котором каждой вершине будет соответствовать не более чем четырёхзначное целое неотрицательное число. Будем соединять две вершины ориентированным ребром, если из одного числа с помощью описанной операции получается другое. В этом графе конечное число вершин, каждая следующая однозначно определяется по предыдущей, поэтому последовательность зациклится. Поскольку в графе 10000 вершин, то длина периода последовательности не превосходит 10000. Улучшим оценку длины периода. Заметим, что если первое число нечётное, то каждое следующее будет нечётным, а если первое число чётное, то каждое следующее будет чётным. Таким образом, все числа в периоде будут иметь одну и ту же чётность, поэтому длина периода не больше, чем 5000.

Задание.

Заполните пропуски в тексте так, чтобы получилось правильное рассуждение.

Улучшим оценку в предыдущем упражнении.
Обозначим первое число через a. Как известно, число даёт при делении на 4 такой же остаток, что и число, образованное его двумя последними цифрами. Следовательно, отбрасывание всех цифр, кроме последних четырёх, не будет влиять на остаток числа при делении на 4. Несложно видеть, что все числа, начиная со второго, будут иметь один и тот же остаток при делении на 4.
Остаток числа a: Остаток остальных чисел:
0 Выбрать (0 или 1, или 2, или 3)
1 Выбрать (0 или 1, или 2, или 3)
2 Выбрать (0 или 1, или 2, или 3)
3 Выбрать (0 или 1, или 2, или 3)
Таким образом, все числа в периоде будут давать одинаковый остаток при делении на 4, поэтому длина периода не превосходит Выбрать (250 или 1000, или 2500).
Ещё улучшим оценку.
Как известно, аналогичное утверждение верно для любой степени двойки, а именно: число даёт такой же остаток при делении на 2^k, как и число, составленное из k его последних цифр. Будем рассматривать остатки чисел в последовательности при делении на Выбрать (8 или 16, или 32). У второго числа остаток будет таким же, как и у числа a^2, у третьего — таким же, как у числа a^4 и т.д.
Если a чётное, то все числа последовательности, начиная Выбрать (со второй или с третьей) , будут давать остаток 0.
Если a нечётное, то несложно убедиться, что все числа последовательности, начиная Выбрать (со второй или с третьей), будут давать остаток 1.
Таким образом, все числа в периоде будут давать одинаковый остаток при делении на Выбрать (8 или 16, или 32), поэтому длина периода не превосходит Выбрать (63 или 125 или 250 или 625).

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

Давайте пойдем по порядку. Первое задание с выбором

Дается некое число «а», которое делим на 4, возможны 4 остатка при делении на 4 (0; 1; 2; 3) и надо определить какие будут остатки у следующих чисел по алгоритму. А следующее число по алгоритму а²

Поехали:

остаток 0; значит a = 4n, тогда а² = (4n)² — делится на 4 и тоже остаток 0 (выбираем 0)

остаток 1; значит a = 4n+1, тогда а² = (4n+1)² = (4n)² + 2•4n + 1 — первые два слагаемых делятся на 4 а третье имеет остаток 1 (выбираем 1)

остаток 2; значит a = 4n+2, тогда а² = (4n+2)² = (4n)² + 2•2•4n + 4 — все слагаемые делятся на 4, значит остаток 0 (выбираем 0)

остаток 3; значит a = 4n+3, тогда а² = (4n+3)² = (4n)² + 2•3•4n + 9 — первые два слагаемых делятся на 4 а третье имеет остаток 1 (выбираем 1)

Таким образом делением на 4 у нас будет участвовать каждое 4-е число. По аналогии с предыдущим описанным решением. Всего было 10000 чисел, потом улучшили до каждого 2-го числа. Стало 5000. Теперь улучшили до каждого 4-го, то есть ещё в 2 раза меньше 5000 : 2 или 10000:4 = 2500 (Выбираем 2500)

Далее ещё улучшают до 2ᵏ, где k количество последних цифр. Но у нас 4-х значное число и каждый раз оставляем 4 последних цифры. Какое же «k» выбрать? Наверное понятно, что максимальное k = 4 и тогда 2⁴ = 2•2•2•2 = 16 (Выбираем 16)

Далее опять проводим анализ. Теперь делитель у нас 16 и предлагается «а» — чётное, то есть a = 2n

Тогда второе число а² = 4n² — не обязательно даст остаток 0, а третье число (a²)² = a⁴ = 2⁴n⁴ = 16n⁴ — даст остаток 0 при делении на 16 (выбираем: с третьей)

если «a» нечётное, то а = 2n+1

Тогда второе число а² = (2n+1)² = 4n² + 4n + 1 — не обязательно даст остаток 1, а третье число (a²)² = (4n² + 4n + 1)² = 16n⁴ + 32n³ + 24n² + 8n + 1 = 16n⁴ + 32n³ + 8n(3n+1) + 1 — первые 2 слагаемых дадут остаток 0 при делении на 16, третье делится на 16, так как или n или 3n+1 кратно 2, и четвертое даст остаток 1. (выбираем: с третьей)

Далее по тексту снова (выбираем 16), ну мы же его выбрали и а него делили.

Поэтому длина периода не превосходит: и снова знаем что делать. Был период 10000. Сначала уменьшили его в 2 раза, когда делили на 2, потом в 4 раза, когда делили на 4.

Теперь делим на 16 (берем каждое 16 число). На сколько же надо разделить, чтоб узнать период? Явно 10000 : 16 = 625 (Выбираем 625)