Polynomials

Why they hold. Each root satisfies its polynomial. For a cubic $x^3 - e_1x^2 + e_2x - e_3$, every root has $r^3 = e_1r^2 - e_2r + e_3$; multiply by $r^{k-3}$ and add over the three roots to get $p_k = e_1p_{k-1} - e_2p_{k-2} + e_3p_{k-3}$ for $k \ge 3$ (with $p_0 = 3$, which is where the $3e_3$ in $p_3$ comes from). So the power sums obey the same linear recurrence as the polynomial, and each is computed from the previous three.

Spotting it. Each root satisfies $r^3 = r + 1$, so the power sums satisfy $p_k = p_{k-2} + p_{k-3}$.

Step 1. $p_0 = 3$, $p_1 = e_1 = 0$, $p_2 = e_1^2 - 2e_2 = 0 - 2(-1) = 2$.

Step 2. $p_3 = p_1 + p_0 = 3$, $p_4 = p_2 + p_1 = 2$, $p_5 = p_3 + p_2 = 5$. The answer is $5$.

Spotting it. Three power sums determine the three elementary symmetric sums, which determine every other power sum. Run Newton forwards to recover $e_2$ and $e_3$, then once more.

Step 1. $p_2 = e_1p_1 - 2e_2$: $5 = 9 - 2e_2$, so $e_2 = 2$.

Step 2. $p_3 = e_1p_2 - e_2p_1 + 3e_3$: $7 = 15 - 6 + 3e_3$, so $e_3 = -\tfrac23$.

Step 3. $p_4 = e_1p_3 - e_2p_2 + e_3p_1 = 21 - 10 - 2 = 9$.

Why it works. Plug $\omega^j$ into $P(x) = \sum a_kx^k$ and average over $j = 0, \dots, n - 1$. The coefficient $a_k$ gets multiplied by $\tfrac1n\sum_j \omega^{jk}$. When $n \mid k$ every term is $1$ and the average is $1$; otherwise it is the average of a full set of rotated roots of unity, which is $0$. To pick out the indices $k \equiv r \pmod n$ instead, average $\omega^{-jr}P(\omega^j)$.

Spotting it. $N = \sum_{3 \mid k}\binom{12}{k}$: every third coefficient of $(1 + x)^{12}$.

Step 1. $N = \tfrac13\left[2^{12} + (1 + \omega)^{12} + (1 + \omega^2)^{12}\right]$.

Step 2. $1 + \omega = -\omega^2$ is a unit complex number at $60^\circ$, so its $12$th power is at $720^\circ$: $(1 + \omega)^{12} = 1$, and likewise $(1 + \omega^2)^{12} = 1$.

Step 3. $N = \tfrac{4096 + 2}{3} = 1366$, and the remainder is $366$.

Spotting it. Encode each element $k$ as a factor $1 + x^k$: the coefficient of $x^s$ in $F(x) = \prod_{k=1}^{9}(1 + x^k)$ counts subsets with sum $s$. Filter the exponents divisible by $3$.

Step 1. Mod $3$ the elements are three $0$s, three $1$s and three $2$s, so at a cube root of unity $\omega$: $F(\omega) = (1 + 1)^3(1 + \omega)^3(1 + \omega^2)^3$.

Step 2. $(1 + \omega)(1 + \omega^2) = 1 + \omega + \omega^2 + \omega^3 = 0 + 1 = 1$, so $F(\omega) = 8$; likewise $F(\omega^2) = 8$. And $F(1) = 2^9 = 512$.

Step 3. The count is $\tfrac13(512 + 8 + 8) = 176$.

AIME problems rarely give the polynomial outright — they give conditions. "The polynomial $p$ of degree $4$ satisfies $p(k) = k^2$ for $k = 1,2,3,4$" is really "$p(x) - x^2$ has roots $1,2,3,4$", so $p(x) = x^2 + c(x-1)(x-2)(x-3)(x-4)$ and one more condition pins $c$. Subtracting the pattern the values follow is the move.

These convert "the sum of the coefficients of $(2x-3)^{10}$" into $(2-3)^{10} = 1$ with no expansion. The roots-of-unity filter is the general form: averaging $p$ over the $n$-th roots of unity keeps only the coefficients whose index is divisible by $n$.

Step 1 — the roots give $p(x) = a(x-1)(x-2)(x-3)$.

Step 2 — $p(0) = a(-1)(-2)(-3) = -6a = -6$, so $a = 1$ (consistent with monic).

Step 3 — $p(4) = (3)(2)(1) = 6$.

Spotting it. The values follow the pattern $k^2$, so $p(x) - x^2$ has roots $1, 2, 3, 4$.

Step 1. $p(x) - x^2$ has degree $4$ and leading coefficient $1$ (the $x^2$ does not touch the $x^4$ term), so $p(x) - x^2 = (x - 1)(x - 2)(x - 3)(x - 4)$.

Step 2. $p(5) = 25 + 4 \cdot 3 \cdot 2 \cdot 1 = 49$.

Spotting it. $p(1)$ adds all the coefficients and $p(-1)$ adds them with alternating signs, so their average keeps only the even powers.

Step 1. $p(1) = 3^6 = 729$ and $p(-1) = (-1)^6 = 1$.

Step 2. The even-power coefficients add to $\tfrac{729 + 1}{2} = 365$.