СПбГУ 2022, 8–9 классы, задача 11
( баллов) Числа от до разбиты на несколько групп. Известно, что если в группе более одного числа, то сумма любых двух чисел из этой группы делится на . Какое наименьшее количество групп может быть?
Ответ
Ответ: .
Решение: При обозначим через множество чисел от до , дающие при делении на остаток . Пусть число из входит в некоторую группу. Если в нее входит еще число , то оно принадлежит , иначе не кратно . Пусть в этой группе есть третье число . Тогда оно лежит и в , и в . Это возможно только при и . Числа, не входящие в и , можно включать только в двухэлементные группы, а всего таких чисел . Значит, они дают не менее групп. Множества и могут образовывать группы, но объединить в одну их нельзя. Таким образом, всего потребуется по крайней мере группы.
Приведем реализацию разбиения на группы. Одной них будет , другой — , а также выберем группы вида , где и .
Верное решение