36-я Международная Математическая OлимпиадаКанада, Торонто, 1995 год

Пусть $p$ — нечетное простое число. Найти количество подмножеств $A$ множества $\{1,2,\ldots ,2p\}$ таких, что:
а) $A$ содержит ровно $p$ элементов;
б) сумма всех элементов из $A$ делится на $p$.

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

Рассмотрим многочлен $f(x,y) = (x+y)(x^2+y) \ldots (x^{2p}+y)$. Заметим, что каждый его одночлен $x^my^k$ соответствует подмножеству $\{1, 2, \ldots, 2p \}$ такому, что сумма его членов равна $m$, а их количество равно $2p-k$. Поэтому нам нужно посчитать сумму коэффициентов при одночленах вида $x^{pk}y^p$.

Пусть $\omega$ - такое число, что $1+\omega + \ldots + \omega^{p-1} = 0$, тогда $\omega^p = 1$ (по другому, это просто корень $p$-ой степени из единицы}

Используя $\textit{roots of unity filter}$, эта сумма равна $\frac{1}{p^2} \sum_{x,y = \{ 1, \omega, \ldots, \omega^{p-1} \} } f(x,y) - 2$, первое слагаемое которой дает сумму коэффициентов при одночленах, степени $x$ и $y$ которых делятся на $p$, но тогда нам нужно отнять два члена, для которых $y$ имеет степень $2p$ или $0$, что соответствует второму слагаемому.

$\frac{1}{p^2} \sum_{x,y = \{ 1, \omega, \ldots, \omega^{p-1} \} } f(x,y) - 2 = \frac{1}{p^2}\sum_{y = \{ 1, \omega, \ldots, \omega^{p-1} \} }(y+1)^{2p} + (p-1)(y+1)^2\ldots(y+\omega^{p-1})^2$, где я воспользовался тем, что $\omega^p = 1$ и $\{1, 2, \ldots, p \} \equiv \{k, 2k, \ldots pk\} (mod p), \forall 1\leq k \leq p$. $y+1, \ldots, y+\omega^{p-1}$ - корни многочлена $(x-y)^p-1$, значит их произведение равно свободному члену, по теореме Виета $\Rightarrow$ $(y+1)^2\ldots(y+\omega^{p-1})^2 = (y^p+1)^2 = 4, \forall y = \{ 1, \omega, \ldots, \omega^{p-1} \}$.

Теперь разберемся с $\sum_{y = \{ 1, \omega, \ldots, \omega^{p-1} \} }(y+1)^{2p}$: По тому же самому $\textit{roots of unity filter}$, это равно сумме коэффициентов этого многочлена при одночленах со степенями кратными $p$, умноженной на $p$, то есть $p(1+C_{2p}^p+1)$, тогда общая сумма равна $\frac{C_{2p}^pp+2p+4p(p-1)}{p^2}-2 = \frac{C_{2p}^p - 2}{p} - 2$

Подробнее про эту технику тут: https://artofproblemsolving.com/community/c1340h1003741_roots_of_unity_filter