Loading [MathJax]/jax/output/SVG/jax.js

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


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

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

пред. Правка 2   7
2 года 3 месяца назад #

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

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

Используя roots of unity filter, эта сумма равна 1p2x,y={1,ω,,ωp1}f(x,y)2, первое слагаемое которой дает сумму коэффициентов при одночленах, степени x и y которых делятся на p, но тогда нам нужно отнять два члена, для которых y имеет степень 2p или 0, что соответствует второму слагаемому.

1p2x,y={1,ω,,ωp1}f(x,y)2=1p2y={1,ω,,ωp1}(y+1)2p+(p1)(y+1)2(y+ωp1)2, где я воспользовался тем, что ωp=1 и {1,2,,p}{k,2k,pk}(modp),1kp. y+1,,y+ωp1 - корни многочлена (xy)p1, значит их произведение равно свободному члену, по теореме Виета (y+1)2(y+ωp1)2=(yp+1)2=4,y={1,ω,,ωp1}.

Теперь разберемся с y={1,ω,,ωp1}(y+1)2p: По тому же самому roots of unity filter, это равно сумме коэффициентов этого многочлена при одночленах со степенями кратными p, умноженной на p, то есть p(1+Cp2p+1), тогда общая сумма равна Cp2pp+2p+4p(p1)p22=Cp2p2p2

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