ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 97870
Темы:    [ Простые числа и их свойства ]
[ Деление с остатком ]
Сложность: 3
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

Автор: Фольклор

Из чисел  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 баллов

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Дата 1984/1985
Номер 6
вариант
Вариант весенний тур, подготовительный вариант, 9-10 класс
Задача
Номер 2

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .