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 题