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$

Answer: C

Concepts:subsets multiplication principle modular arithmetic

Difficulty rating: 2520

Small Hint:

For a fixed $n,$ each of the $10$ elements independently chooses the first set it enters, or never enters

Big Hint:

That gives $(n+1)^{10}$ chains, so $K=\sum_{k=2}^{11}k^{10};$ reduce each term modulo $10$

Solution:

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 Problem 24

Answer: C

Difficulty rating: 2520

Small Hint:

Big Hint:

Solution:

Problem 24 in Other Years