Задача с вош Муницип
В бесконечной возрастающей последовательности a1, a2, ... натуральных чисел любые 2 соседних числа отличаются не более чем на миллион. Верно ли, что можно выбрать миллион членов этой последовательности так, чтобы их наибольшой общий делитель был больше миллиона?
Покажем, как можно прийти к решению этой задачи на маленьком примере: пусть вместо миллиона будет число 5.
1) Начнём рассуждать последовательно. Если разобьём все натуральные числа на отрезки по 5 штук, то ясно, что в каждом отрезке найдётся хотя бы одно наше число. Поэтому из наших чисел можно выбрать бесконечную последовательность таких, которые имеют одинаковый остаток от деления на 5 - к примеру, остаток 3. Т.е. числа вида 5n + 3. Тогда, если бы мы могли выбрать только n, кратные 3, то все выбранные числа делились бы на 3.
2) Предыдущее рассуждение имеет два недостатка. Во-первых, нам нужно деление не на 3, а на число, большее 5. Поэтому мы объединим два последовательных отрезка по 5 чисел в один отрезок из 10 чисел. В каждом таком большом отрезке хотя бы одно число попадёт в "старшую" его половину (от 6 до 10), т.е. имеет вид: 10n + r, где остаток r ∊ {6, 7, 8, 9, 0}. Итак, теперь мы можем выбрать бесконечную последовательность чисел, имеющих одинаковый остаток от деления на 10, и этот остаток уже больше 5 или равен 0. Если r = 0, то задача решена (все числа делятся на 10), так что считаем, что r > 5. Пусть, к примеру, r = 7.
3) Во-вторых, в подпоследовательности чисел с остатком 7 (т.е. вида 10n + 7) необязательно встретятся n, кратные 7. Поэтому вместо всех подряд отрезков по 10 чисел мы будем рассматривать только каждый (6·7·8·9)-ый такой отрезок. Тогда внутри таких отрезков мы можем выбрать бесконечную последовательности чисел, имеющих одинаковый остаток r > 5. Все эти числа имеют вид: 10·9·8·7·6·n + r. И уже они все делятся на r.
-------------------------------------------------
Решение кратко.
Пусть n = 1000000. Разобьём ряд натуральных чисел на последовательные отрезки по 2n чисел. Первый отрезок в дальнейшем исключим. Построим бесконечную последовательность чисел, делящихся на одно и то же из следующих чисел: (n+1), (n+2), ..., (2n-1) или 2n.
Обозначим k = (n+1)(n+2)...(2n-1). Выберем отрезки с номерами k, 2k, 3k и т.д. На каждом таком отрезке, в "старшей" его половине, найдётся хотя бы одно число из исходной последовательности. Из таких чисел можно выбрать бесконечную последовательность, имеющих один и тот же остаток от деления на 2n — все они имеют вид: (2n)k + r. Если r = 0, то все эти числа делятся на 2n. Иначе все они делятся на r > n.
да
Chatgpt