2021 AMC Fall 10B Problem 22

Expanding $(1 + 2 + \cdots + n)^2$ gives every $j^2$ once and every product $jk$ with $j \ne k$ twice, so
$$S_n = \frac{(1 + \cdots + n)^2 - (1^2 + \cdots + n^2)}{2} = \frac12\left[\frac{n^2(n+1)^2}{4} - \frac{n(n+1)(2n+1)}{6}\right].$$
Factor out $\frac{n(n+1)}{12}$ inside the bracket: $\frac{n(n+1)}{12}\left[3n(n+1) - 2(2n+1)\right] = \frac{n(n+1)(3n^2 - n - 2)}{12}$, and $3n^2 - n - 2 = (n-1)(3n+2)$. Hence
$$S_n = \frac{(n-1)\,n\,(n+1)\,(3n+2)}{24}.$$

Since $24 = 8 \cdot 3$, $S_n$ is divisible by $3$ exactly when the numerator is divisible by $9$. The factor $3n + 2$ is never a multiple of $3$, so we need $9 \mid (n-1)n(n+1)$. At most one of three consecutive integers is a multiple of $3$, so one of them must be a multiple of $9$: $n \equiv 0, 1,$ or $8 \pmod 9$.

The ten smallest such $n \ge 2$ are $8, 9, 10, 17, 18, 19, 26, 27, 28, 35$, with sum
$$27 + 54 + 81 + 35 = 197.$$

The answer is $\boxed{\textbf{(B)}\ 197}$.

"Sum of pairwise products" is always $\frac{(\text{sum})^2 - \text{sum of squares}}{2}$; the closed form then reveals the arithmetic. The subtle step is that a factor of $3$ in the denominator raises the requirement from $3 \mid$ numerator to $9 \mid$ numerator. Quick check: $S_2 = 2$ and $S_3 = 11$ are not multiples of $3$, while $S_8 = 546 = 3 \cdot 182$ is.

Work mod $3$ recursively: $S_n = S_{n-1} + n(1 + \cdots + (n-1)) = S_{n-1} + \frac{n^2(n-1)}{2}$. Computing residues for $n = 2, 3, \dots$ gives $2, 2, 2, 2, 1, 1, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, \dots$, with period $9$ and zeros at $n \equiv 8, 0, 1 \pmod 9$; this confirms the list.

• Forgetting that the division by 24 eats one factor of 3, and concluding S_n is always divisible by 3 because n-1, n, n+1 always contain a multiple of 3.
• Including $n = 1$ (where $S_1 = 0$) even though the problem requires $n \ge 2$, which shifts the list and the sum.