MathDB
suspiciously sequenced sub-sets

Source: 2023 AMC12A #24

November 9, 2023
AMCAMC 122023 AMC2023 AMC 12ASequencesremainderSets

Problem Statement

Let KK be the number of sequences A1A_1, A2A_2, \dots, AnA_n such that nn is a positive integer less than or equal to 1010, each AiA_i is a subset of {1,2,3,,10}\{1, 2, 3, \dots, 10\}, and Ai1A_{i-1} is a subset of AiA_i for each ii between 22 and nn, 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=5n = 5. What is the remainder when KK is divided by 1010?
<spanclass=latexbold>(A)</span>1<spanclass=latexbold>(B)</span>3<spanclass=latexbold>(C)</span>5<spanclass=latexbold>(D)</span>7<spanclass=latexbold>(E)</span>9<span class='latex-bold'>(A) </span> 1 \qquad <span class='latex-bold'>(B) </span> 3 \qquad <span class='latex-bold'>(C) </span> 5 \qquad <span class='latex-bold'>(D) </span> 7 \qquad <span class='latex-bold'>(E) </span> 9