Задача 97870
|
|
 |
Условие
Из чисел 1, 2, 3, ..., 1985 выбрать наибольшее количество чисел так, чтобы разность любых двух выбранных чисел не была простым числом.
Решение
Пример. Выберем все числа вида 4k + 1 (их 497). Разность каждых двух из них делится на 4 и, следовательно, не является простым числом.
Оценка. Пусть выбрано число n. Тогда числа n + 2, n + 3, n + 5, n + 7 выбрать уже нельзя. А среди чисел n + 1, n + 4, n + 6 можно выбрать лишь одно. (Разность любых двух из них – простое число.) Это значит, что из любых восьми подряд идущих чисел мы можем выбрать не более двух. Числа от 1 до 1984 можно разбить на 248 восьмёрок. Поэтому выбрать можно не более 2·248 + 1 = 497 чисел.
Замечания
6 баллов
