2021 AMC Fall 10B Problem 22

Small case first. For $n = 3$ the products are $1 \times 2$, $1 \times 3$, $2 \times 3$, so $S_3 = 2 + 3 + 6 = 11$. Now square the sum $1 + 2 + 3 = 6$:
$$(1 + 2 + 3)^2 = 1^2 + 2^2 + 3^2 + 2(1 \times 2 + 1 \times 3 + 2 \times 3) = 14 + 2 \times 11 = 36.$$
Squaring the sum gives each square once and each product twice. That is the key to a formula.

1. Formula. In general,
$$S_n = \frac{(1 + 2 + \cdots + n)^2 - (1^2 + 2^2 + \cdots + n^2)}{2}.$$
Using $1 + \cdots + n = \frac{n(n+1)}{2}$ and $1^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}$, then pulling out the common factor $\frac{n(n+1)}{24}$:
$$S_n = \frac{n(n+1)}{24}\bigl[3n(n+1) - 2(2n+1)\bigr] = \frac{n(n+1)(3n^2 - n - 2)}{24} = \frac{(n-1)\,n\,(n+1)\,(3n+2)}{24}.$$
Check with $n = 3$: $\frac{2 \times 3 \times 4 \times 11}{24} = 11$. Good.
2. When is $S_n$ a multiple of 3? The bottom is $24 = 8 \times 3$. For $S_n$ to still have a factor of $3$ after dividing, the top needs two factors of $3$, that is, it must be a multiple of $9$.
3. Where can the factors of 3 come from? Not from $3n + 2$: it always leaves remainder $2$ when divided by $3$. So $(n-1) \times n \times (n+1)$ must be a multiple of $9$. Among three numbers in a row, exactly one is a multiple of $3$, so that one must be a multiple of $9$.
4. So one of $n - 1$, $n$, $n + 1$ is a multiple of $9$. In other words, $n$ is one less than a multiple of $9$, a multiple of $9$, or one more than a multiple of $9$. Listing from the smallest ($n$ starts at $2$):
$$8, 9, 10,\quad 17, 18, 19,\quad 26, 27, 28,\quad 35.$$
5. Add them. Each group of three adds to three times its middle number: $27 + 54 + 81 + 35 = 197$.

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

"Add up all products of two different numbers from a list" always equals (sum squared minus sum of squares) divided by $2$. After that, the problem is about factors of $3$. The subtle point is that a $3$ on the bottom of the fraction raises the bar: the top needs a factor of $9$, not just $3$.

Build $S_n$ one step at a time and track only the remainder when dividing by $3$. Going from $n - 1$ to $n$ adds the new products $1 \times n, 2 \times n, \ldots, (n-1) \times n$, which total $n \times \frac{(n-1)n}{2}$.

The remainders repeat every $9$ steps, with $0$ at $n = 8, 9, 10$, then $17, 18, 19$, and so on. This matches the list above.

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}$.