Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2023 AMC 12A Problems/Problem 24

Revision as of 11:23, 10 November 2023 by Quantum-phantom (talk | contribs)

Problem

Let $K$ be the number of sequences $A_1$, $A_2$, $\dots$, $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, \dots, 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$?

$\textbf{(A) } 1 \qquad \textbf{(B) } 3 \qquad \textbf{(C) } 5 \qquad \textbf{(D) } 7 \qquad \textbf{(E) } 9$

Solution 1

Consider any sequence with $n$ terms. Every 10 number has such choices: never appear, appear the first time in the first spot, appear the first time in the second spot… and appear the first time in the $n$th spot, which means every number has $(n+1)$ choices to show up in the sequence. Consequently, for each sequence with length $n$, there are $(n+1)^{10}$ possible ways.

Thus, the desired value is $\sum_{i=1}^{10}(i+1)^{10}\equiv \boxed{\textbf{(C) } 5}\pmod{10}$

~bluesoul

Solution 2

Let $f(x,\ell)$ be the number of sequences $A_1$, $A_2$, $\dots$, $A_\ell$ such that each $A_i$ is a subset of $\{1, 2,\dots,x\}$, and $A_i$ is a subset of $A_{i+1}$ for $i=1$, $2\dots$, $\ell-1$. Then $f(x,1)=2^x$ and $f(0,\ell)=1$.

If $\ell\ge2$ and $x\ge1$, we need to get a recursive formula for $f(x,\ell)$: If $|A_1|=i$, then $A_1$ has $\text C_x^i$ possibilities, and the subsequence $\{A_i\}_{2\le i\le\ell}$ has $f(x-i,\ell-1)$ possibilities. Hence $f(x,\ell)=$ \[f(x,\ell)=\sum_{i=0}^x\text C_x^if(x-i,\ell-1).\] By applying this formula and only considering modulo $10$, we get $f(1,2)=3$, $f(1,3)=4$, $f(1,4)=5$, $f(1,5)=6$, $f(1,6)=7$, $f(1,7)=8$, $f(1,8)=9$, $f(1,9)=0$, $f(1,10)=1$, $f(2,2)=9$, $f(2,3)=6$, $f(2,4)=5$, $f(2,5)=6$, $f(2,6)=9$, $f(2,7)=4$, $f(2,8)=1$, $f(2,9)=0$, $f(2,10)=1$, $f(3,2)=7$, $f(3,3)=4$, $f(3,4)=5$, $f(3,5)=6$, $f(3,6)=3$, $f(3,7)=2$, $f(3,8)=9$, $f(3,9)=0$, $f(3,10)=1$, $f(4,2)=1$, $f(4,3)=6$, $f(4,4)=5$, $f(4,5)=6$, $f(4,6)=1$, $f(4,7)=6$, $f(4,8)=1$, $f(4,9)=0$, $f(4,10)=1$, $f(5,2)=3$, $f(5,3)=4$, $f(5,4)=5$, $f(5,5)=6$, $f(5,6)=7$, $f(5,7)=8$, $f(5,8)=9$, $f(5,9)=0$, $f(5,10)=1$, $f(6,2)=9$, $f(6,3)=6$, $f(6,4)=5$, $f(6,5)=6$, $f(6,6)=9$, $f(6,7)=4$, $f(6,8)=1$, $f(6,9)=0$, $f(6,10)=1$, $f(7,2)=7$, $f(7,3)=4$, $f(7,4)=5$, $f(7,5)=6$, $f(7,6)=3$, $f(7,7)=2$, $f(7,8)=9$, $f(7,9)=0$, $f(7,10)=1$, $f(8,2)=1$, $f(8,3)=6$, $f(8,4)=5$, $f(8,5)=6$, $f(8,6)=1$, $f(8,7)=6$, $f(8,8)=1$, $f(8,9)=0$, $f(8,10)=1$, $f(9,2)=3$, $f(9,3)=4$, $f(9,4)=5$, $f(9,5)=6$, $f(9,6)=7$, $f(9,7)=8$, $f(9,8)=9$, $f(9,9)=0$, $f(9,10)=1$, $f(10,2)=9$, $f(10,3)=6$, $f(10,4)=5$, $f(10,5)=6$, $f(10,6)=9$, $f(10,7)=4$, $f(10,8)=1$, $f(10,9)=0$, $f(10,10)=1$.

Lastly, we get $K\equiv\textstyle\sum\limits_{i=1}^{10}f(10,i)\equiv\boxed{\textbf{(C) } 5}\pmod{10}$. ~Quantum-Phantom

Video Solution 1 by OmegaLearn

https://youtu.be/0LLQW0XCKsQ


See also

2023 AMC 12A (Problems • Answer Key • Resources)
Preceded by
Problem 23 		Followed by
Problem 25
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2023_AMC_12A_Problems/Problem_24&oldid=201874"