2023 AMC 12A Problem 24

Question

Let

K

be the number of sequences

A_1,

A_2,

\ldots,

A_n

such that

n

is a positive integer less than or equal to

10,

each

A_i

is a subset of

\{1,2,3,\ldots,10\},

and

A_{i-1}

is a subset of

A_i

for each

i

between

2

and

n,

inclusive. For example,

\{\},

\{5,7\},

\{2,5,7\},

\{2,5,7\},

\{2,5,6,7,9\}

is one such sequence, with

n=5.

What is the remainder when

K

is divided by

10?

1

3

5

7

9

For a fixed

n,

each of the

10

elements independently chooses the first set it enters, or never enters

That gives

(n+1)^{10}

chains, so

K=\sum_{k=2}^{11}k^{10};

reduce each term modulo

10

For a fixed length

n,

each element of

\{1,\ldots,10\}

independently either never appears or first appears in one of

A_1,\ldots,A_n,

giving

n+1

choices. Hence there are

(n+1)^{10}

chains of length

n.

Summing,

K=\sum_{n=1}^{10}(n+1)^{10}=\sum_{k=2}^{11}k^{10}.

Modulo

10,

the terms

k=2,\ldots,11

reduce to

4,9,6,5,6,9,4,1,0,1,

which sum to

45\equiv 5.

Thus, the correct answer is C.

Problem 24 in other years