ПВГ 2023, 10 класс, задача 6

Сложная

Теория чисел

Прогрессии

Источник:

Покори Воробьёвы горы!, Отборочный этап, 2023, 10 класс

Последовательность целых чисел задана рекуррентно: , ,

Найти , где это наибольший общий делитель и . Здесь — произведение всех натуральных чисел от до . Например, , .

Ответ

Ответ: .

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

Найти , где это наибольший общий делитель и .

Получим рекуррентную формулу:

Действительно, из формул имеем:

С другой стороны, , откуда

Аналогично,

Учитывая, что , получаем искомое соотношение и для нечетных индексов:

Тогда

Для нашего примера . Откуда приходим к ответу: .

Похожие задачи

ПВГ 2023, 11 класс, задача 9 (творческая III)

Последовательность целых чисел задана рекуррентно: x₀=0, x₁=1, x_2k=2 · x_2k-1-x_2k-2,qquad x_2k+1=3 · x_2k-x_2k-1. Найти operatorname{НОД}(x₁₄₂₈,x₁₇₁₆), где operatorname{НОД}(a,b) это наибольший

Сложная

Теория чисел

Прогрессии

ПВГ 2025, 10 класс, задача 2

Пусть {x₁,x₂,ldots} - строго возрастающая последовательность натуральных чисел (т.е. x₁23n). Известно, что x₁=1 и x_n-1 · x_n+1=x_n³+1 при всех n>1. Найдите x₅.

Сложная

Теория чисел

Прогрессии

ПВГ 2025, 7–9 классы, задача 6 (7–8), задача 4 (9)

Пусть {x₁,x₂,ldots} - строго возрастающая последовательность натуральных чисел (т.е. x₁23n). Известно, что x₁=1 и x_n-1 · x_n+1=x_n³+1 при всех n>1. Найдите x₄.

Сложная

Теория чисел

Прогрессии

ПВГ 2022, 10–11 классы, задача 9 (творческая III)

Коридор имеет ширину 3 и длину n. Имеется паркетная плитка двух размеров: 1 × 2 и 2 × 2. Найдите количество способов уложить паркет на пол в этом коридоре. В ответе укажите две последние цифры найденного числа (например, если получено число 1234567, то в ответе следует указать 67). n=2022.

Сложная

Прогрессии

Комбинаторика