2021 AMC 10B Fall Problem 22

Question

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?

\ 196

\ 197

\ 198

\ 199

\ 200

Answer: B

Concepts:modular arithmetic summation pattern recognition

Difficulty rating: 1950

Small hint:

Find how

S_n

changes when terms with

k=n

are added

Big hint:

Only

n\equiv2\pmod3

changes the value modulo

3

Solution:

When passing from

S_{n-1}

to

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

or

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

in

n.

The ten least values are

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