2023 AMC 12A 第 24 题

Question

设

K

为满足以下条件的序列

A_1

，

A_2

，

\ldots

，

A_n

的数量：

n

是不超过

10

的正整数，每个

A_i

都是

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

的子集，并且对每个介于

2

和

n

之间（含端点）的

i

，都有

A_{i-1}

是

A_i

的子集。例如，

\{\}

、

\{5,7\}

、

\{2,5,7\}

、

\{2,5,7\}

、

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

是这样一个序列，其中

n=5

。

K

除以

10

的余数是多少？

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

答案：C

知识点：子集乘法原理模运算

难度评级：2520

小提示：

对固定的

n

，这

10

个元素各自独立选择第一次进入哪个集合，或选择永不进入

For a fixed

n,

each of the

10

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

大提示：

这给出

(n+1)^{10}

条链，所以

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

；把每项模

10

化简

That gives

(n+1)^{10}

chains, so

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

reduce each term modulo

10

解答：

对固定长度

n

，

\{1,\ldots,10\}

中的每个元素可以独立选择永不出现，或第一次出现在

A_1,\ldots,A_n

中的某一个，因此每个元素有

n+1

种选择。于是长度为

n

的链有

(n+1)^{10}

条。

因此

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

模

10

时，

k=2,\ldots,11

各项化为

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

，和为

45\equiv 5

。

所以正确答案是 C。

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.

2023 AMC 12A 第 24 题

答案：C

难度评级：2520

小提示：

大提示：

解答：

其他年份的第 24 题