Интересная задача с неизвестным результатом.
Добавлено: Чт, 07 сен 2006, 7:53
Пусть множество A = {1, 2, ... , n-1}. Чему равно количество подмножеств A, в которых сумма элементов кратна n?
Ответом является
SUM ( phi(d) * 2^(n/d) ) / (2*n)
где phi() - функция Эйлера, а сумма берется по всем нечётным делителям d числа n.
Доказать это можно, например, через мультисекцию производящей функции
f(x) = (1+x)*(1+x^2)*...*(1+x^(n-1))