Олимпиада имени Леонарда Эйлера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, поэтому простых чисел среди выбранных Дашей не больше пяти. Пример, когда их ровно пять, дан в первом решении.

Так как простые числа кроме $2$ дают остаток $1$ или $3$ при делений на $4$. По пробуем сделать порядок из шести простых чисел. Что бы это было корректно нам нужно выбрать простые числа которые дадут равные остатки при делений на 4. Посмотрим сначала на числа которые дадут остаток $3$ при делений на $4$.

$3$,$7$, $11$ , $19$ , $23$ а дальше у же нету таких простых чисел.

Теперь рассмотрим простые числа которые дадут остаток $1$ при делений на $4$.

$5$ , $13$ , $17$ а дальше уже нету простых чисел которые дадут остаток $1$ при делений на $4$.

Значит максимальное число простых чисел которые соответстуют по условию равна $5$.