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