Какое наибольшее количество чисел можно выбрать из отрезка натурального ряда от 1 до 2009 так, чтобы разность любых двух из них не была простой?

  Решение:

  Предположим, что мы нашли как выбрать наибольшее количество чисел из отрезка натурального ряда от 1 до 2009 так, чтобы разность любых двух из них не была простой. Если окажется, что наименьшее выбранное число не единица, то "сдвинем" все выбранные числа влево, сохраняя разность между любыми соседними. Получится новая последовательность той же длины, что и первоначально выбранная, но начинаться она будет с единицы. Так как в этой задаче важны не сами числа, а их взаимное расположение, то все числа этой новой последовательности будут удовлетворять условиям задачи.

  С первым числом мы определились. Какое число выбрать вторым? Если пропустить 2, то ближайшее число, которое мы сможем выбрать, это 5, ближайшее следующее - 9... Получаем последовательность

b_k = 4k − 3, причём b₅₀₃ = 2009.

  Разности между любыми двумя такими числами - чётные, причём не равные двум, то есть, не простые.

  Мы показали, как можно выбрать 503 числа. Докажем, что большее количество чисел выбрать нельзя.

  Убедимся, что из любых восьми подряд идущих чисел больше двух выбрать не удаётся. Действительно, вот возможные пары для первой восьмёрки чисел: 1 и 2, 1 и 5, 1 и 7. Трёх и более чисел выбрать не удалось. Числа от 1 до 2008 разобьём на 251 восьмёрку. В любой из них разности между числами такие же, как и у первой восьмёрки. Следовательно, больше, чем 502 числа выбрать из них мы не сможем. 503-м можно выбрать число 2009, что мы и сделали выше.

  Ответ: 503.