Solution
Subsets Divisible by Eleven
Show the problem again
How many subsets of {1, 2, ..., 10} (including the empty set, whose sum is 0) have an element sum divisible by 11? Give an integer.
Worked solution
The answer is 94. Let $\zeta = e^{2\pi i/11}$. The count is $\frac{1}{11}\sum_{j=0}^{10} \prod_{k=1}^{10}(1 + \zeta^{jk})$. The $j = 0$ term is $2^{10} = 1024$. For $j \neq 0$, $k \mapsto jk$ permutes the nonzero residues mod 11, so each such term equals $Q = \prod_{k=1}^{10}(1 + \zeta^k)$. To find $Q$, use $x^{11} - 1 = \prod_{k=0}^{10}(x - \zeta^k)$ at $x = -1$: $-2 = \prod_{k=0}^{10}(-1 - \zeta^k) = -\prod_{k=0}^{10}(1 + \zeta^k) = -2Q$, so $Q = 1$. The count is $(1024 + 10 \cdot 1)/11 = 1034/11 = 94$.
Source: Original problem written for AxiomIQ.