2021 Fall AMC 10B Problem 22

Problem 22 of 25HarderAlgebra Number Theory

For each integer

n\ge2,

let

S_n

be the sum of all products

jk,

where

j

and

k

are integers and

1\le j<k\le n.

What is the sum of the

10

least values of

n

such that

S_n

is divisible by

3?

Show solution

Solution

When passing from

S_{n-1}

S_n,

the new terms are

jn

for

1\le j\lt n.

Their sum is

\begin{gathered} n(1+2+\cdots+(n-1))\\ =\frac{n^2(n-1)}2. \end{gathered}

Modulo

3,

this increment is

0

when

n\equiv0

1\pmod3,

and is

2

when

n\equiv2\pmod3.

Since

S_2=2,

the sequence becomes divisible by

3

after the third occurrence of a number congruent to

2\pmod3,

namely at

n=8.

Then

S_n

stays divisible by

3

for

n=8,9,10,

and the same pattern repeats every

9

n.

The ten least values are

8,9,10,17,18,19,26,27,28,35.

Their sum is

197.

Thus, the answer is B .