Областная олимпиада по математике, 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$.

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