Задача 5
Какое наибольшее количество чисел можно выбрать из отрезка натурального ряда 1, 2, 3, …, 2025 так, чтобы разность любых двух выбранных чисел не была простым числом?
Решение.
Для того чтобы понять, каким образом условие «непростоты» всех разностей связано с количеством чисел, которое можно выбрать, рассмотрим какую-нибудь небольшую группу подряд идущих чисел. Легко видеть, что, например, для 5 чисел n, n+1, n+2, n+3, n+4 можно выбрать только два числа, удовлетворяющих условию задачи: все остальные разности дают простое число.
Попытаемся расширить группу чисел. Для группы из 6, 7 и 8 чисел получаем всё то же количество выбранных чисел — два. Докажем, что из любых восьми подряд идущих чисел можно выбрать не более двух. Пусть выбрано число n. Тогда числа n+2, n+3, n+5, n+7 выбрать уже нельзя. А среди чисел n+1, n+4, n+6 можно выбрать только одно, поскольку разность любых двух из них — простое число.
Для 9 чисел получаем, что можно выбрать уже три числа, для 13 — четыре, для 17 — пять и т.д., причём можем явно указать эти числа: они дают остаток 1 при делении на 4. Делаем вывод, что группы из 4 чисел являются оптимальными при разделении всей массы из 2025 чисел на подгруппы.
2025 = 506·4 + 1. Имеем 506 чисел вида 4k+1 (включая число 2025). Таким образом, мы установили, что удовлетворяющих условию задачи чисел не более чем 506, и, с другой стороны, нашли 506 таких числа: разность любых двух из них делится на 4 и, значит, не является простым числом.
Ответ: 506.