Областная олимпиада по математике, 2023 год, 10 класс

На карточках написаны $0,1,2, \ldots, p-1$, где $p$ - простое. Сколькими способами можно выбрать несколько карточек так чтобы сумма чисел на карточках делилась на р?

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

Рассмотрим некоторое подмножество $0,1,...,p-1$(остатки по модулю $p$) из $p>k>0$ чисел с суммой всех его элементов $s$. Увеличим все его элементы на 1, тогда сумма его элементов будет равна $s+k$. Повторим операцию ещё $p-2$ раза и получим $p$ наборов с суммами $s,s+k,s+2k,...,s+(p-1)k$. Они образуют полную систему вычетов по модулю $p$, а значит ровно одна из них делится на $p$. Разобьём все наборы из $k$ элементов на такие группы из $p$ наборов. Количество $k$-элементных подмножеств элементов равно $(^p_k)$, выбрав из каждой группы наборы с суммами, делящимися на $p$, получаем $\frac{(^p_k)}p$ наборов. Поэтому искомое количество равно $\frac{(^p_1)}p+\frac{(^p_2)}p+...+\frac{(^p_{p-1})}p+1=\frac{2^p-2}p+1$

Рассмотрим многочлен $f(x)=(x^0+1)(x^1+1)\dots(x^{p-1}+1)$. Тогда искомое количество равно сумме коэффициентов при одночленах вида $x^{pk}, k>0$. Воспользуемся техникой roots of unity filter. Пусть $\omega$ - корень из 1, то есть $1+\omega^1+\dots+\omega^{p-1}=0\Rightarrow \omega^p=1$ и $S=\{1,\omega^1,\dots,\omega^{p-1}\}$. Тогда искомая сумма равна $\frac1p\sum_{x\in S} f(x)-1$. В свою очередь $$\sum_{x\in S} f(x)=f(1)+(p-1)(\omega^0+1)(\omega^1+1)\dots(\omega^{p-1}+1)=2^p+2p-2$$$\prod(\omega^i+1)$ посчитаем, как произведение корней уравнения $(x-1)^p-1$, по теореме Виета оно противоположно свободному члену -2. Таким образом ответ $\frac{2^p-2}p+1$.

Аналогичное решение

Введем понятие $C_{(k,r)} -$ количество $k-$ элементых подмножеств, сумма элементов у каждого при делении на $p$ дает остаток $r$. Будем рассматривать $1\leq k \leq p-1$.

Докажем, что $C_{(k,0)} = C_{(k,i)}$ для любого $0≤i≤p-1$.

Рассмотрим любое подмножество $A= {x_1, x_2,...,x_k}, \sum \limits_{i=1}^{k}{x_i} \equiv 0 \pmod {p}$. Тогда рассмотрим сдвиг каждого элемента на $l$ по модулю $p$. ( т.е $x_i => x_i + l$)

Очевидно, что множества не совпадают т.к $lk$ не может давать $0$ по модулю $p$. Также такой $l$ существует, такой что $lk \equiv i \pmod {p}$. Так как $lk$ дает полную систему остатков при $0 \leq l \leq p-1$. Отсюда следует биекция между подмножествами. Откуда всего вариантов выбрать $ \sum \limits_{k=1}^{p-1}{C_{(k,0)}} = \dfrac{2^p-2}{p}$, при $1 \leq k \leq p-1$. Осталось добавить $C_{(p,0)}=1$. Отсюда и ответ:

$\dfrac{2^p-2}{p} +1$.