Олимпиада имени Леонарда Эйлера2014-2015 учебный год, I тур дистанционного этапа

Из натуральных чисел от 1 до 25 Даша выбрала шесть таких, что разность любых двух выбранных чисел кратна 4. Какое наибольшее количество простых чисел могла выбрать Даша?

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ: Пять.
Разность двух чисел делится на 4 тогда и только тогда, когда эти числа имеют одинаковые остатки от деления на 4. Выпишем все простые числа, меньшие 25, и их остатки от деления на 4: 2-2, 3-3, 5-1, 7-3, 11-3, 13-1, 17-1, 19-3, 23-3. Больше всего — пять простых чисел с остатком 3, что и даёт ответ.

Комментарии от администратора Комментарии от администратора №2.     Так как $5-2 = 3,13-11 = 19-17 =2$, из групп простых чисел $\{2, 3, 5\}$, $\{11, 13\}$, $\{17, 19\}$ Даша могла выбрать не больше, чем по одному числу. Из простых, меньших 25, в эти группы не входят только числа 7 и 23, поэтому простых чисел среди выбранных Дашей не больше пяти. Пример, когда их ровно пять, дан в первом решении.