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$ ， $\{1,\ldots,10\}$ 中的每个元素可以独立选择永不出现，或第一次出现在 $A_1,\ldots,A_n$ 中的某一个，因此每个元素有 $n+1$ 种选择。于是长度为 $n$ 的链有 $(n+1)^{10}$ 条。

因此模 $10$ 时， $k=2,\ldots,11$ 各项化为 $4,9,6,5,6,9,4,1,0,1$ ，和为 $45\equiv 5$ 。 $K=\sum_{n=1}^{10}(n+1)^{10}=\sum_{k=2}^{11}k^{10}.$

所以正确答案是 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 题