36-я Международная Математическая Oлимпиада
Канада, Торонто, 1995 год
а) A содержит ровно p элементов;
б) сумма всех элементов из A делится на p.
Комментарий/решение:
Рассмотрим многочлен f(x,y)=(x+y)(x2+y)…(x2p+y). Заметим, что каждый его одночлен xmyk соответствует подмножеству {1,2,…,2p} такому, что сумма его членов равна m, а их количество равно 2p−k. Поэтому нам нужно посчитать сумму коэффициентов при одночленах вида xpkyp.
Пусть ω - такое число, что 1+ω+…+ωp−1=0, тогда ωp=1 (по другому, это просто корень p-ой степени из единицы}
Используя roots of unity filter, эта сумма равна 1p2∑x,y={1,ω,…,ωp−1}f(x,y)−2, первое слагаемое которой дает сумму коэффициентов при одночленах, степени x и y которых делятся на p, но тогда нам нужно отнять два члена, для которых y имеет степень 2p или 0, что соответствует второму слагаемому.
1p2∑x,y={1,ω,…,ωp−1}f(x,y)−2=1p2∑y={1,ω,…,ωp−1}(y+1)2p+(p−1)(y+1)2…(y+ωp−1)2, где я воспользовался тем, что ωp=1 и {1,2,…,p}≡{k,2k,…pk}(modp),∀1≤k≤p. y+1,…,y+ωp−1 - корни многочлена (x−y)p−1, значит их произведение равно свободному члену, по теореме Виета ⇒ (y+1)2…(y+ωp−1)2=(yp+1)2=4,∀y={1,ω,…,ωp−1}.
Теперь разберемся с ∑y={1,ω,…,ωp−1}(y+1)2p: По тому же самому roots of unity filter, это равно сумме коэффициентов этого многочлена при одночленах со степенями кратными p, умноженной на p, то есть p(1+Cp2p+1), тогда общая сумма равна Cp2pp+2p+4p(p−1)p2−2=Cp2p−2p−2
Подробнее про эту технику тут: https://artofproblemsolving.com/community/c1340h1003741_roots_of_unity_filter
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.