Skip to main content

2023 AMC 12A Problem 24

Problem 24 of 25HarderNumber TheoryCounting & Probability

Let KK be the number of sequences A1,A_1, A2,A_2, ,\ldots, AnA_n such that nn is a positive integer less than or equal to 10,10, each AiA_i is a subset of {1,2,3,,10},\{1,2,3,\ldots,10\}, and Ai1A_{i-1} is a subset of AiA_i for each ii between 22 and n,n, inclusive. For example, {},\{\}, {5,7},\{5,7\}, {2,5,7},\{2,5,7\}, {2,5,7},\{2,5,7\}, {2,5,6,7,9}\{2,5,6,7,9\} is one such sequence, with n=5.n=5. What is the remainder when KK is divided by 10?10?

Answer choices

Show solution

Solution

For a fixed length n,n, each element of {1,,10}\{1,\ldots,10\} independently either never appears or first appears in one of A1,,An,A_1,\ldots,A_n, giving n+1n+1 choices. Hence there are (n+1)10(n+1)^{10} chains of length n.n. Summing, K=n=110(n+1)10=k=211k10. K=\sum_{n=1}^{10}(n+1)^{10}=\sum_{k=2}^{11}k^{10}. Modulo 10,10, the terms k=2,,11k=2,\ldots,11 reduce to 4,9,6,5,6,9,4,1,0,1,4,9,6,5,6,9,4,1,0,1, which sum to 455.45\equiv 5. Thus, the correct answer is C.

More practice

Concepts: subsets · multiplication principle · modular arithmetic

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.