СПбГУ 2023, 10–11 классы, задача 9

Ответ: .

Решение. Приведем пример. Можно выбрать все числа, кратные . Тогда разность любых двух чисел будет также кратна , а числа , и не кратны .

Оценка строится из того соображения, что среди последовательных чисел не может быть выбрано числа. Докажем это утверждение. Возьмем какое-либо выбранное число и пять чисел, следующих за ним. Тогда точно не выбраны второе, пятое и шестое. Остаются третье и четвертое числа, но они не могут быть выбраны оба сразу. Среди пяти и менее последовательных чисел выбрать числа тем более невозможно.