Question

Sea $K$ el número de sucesiones $A_1,A_2,\ldots,A_n$ tales que $n$ es un entero positivo menor o igual que $10,$ cada $A_i$ es un subconjunto de $\{1,2,3,\ldots,10\},$ y $A_{i-1}$ es un subconjunto de $A_i$ para cada $i$ entre $2$ y $n,$ inclusive. Por ejemplo, $\{\},$ $\{5,7\},$ $\{2,5,7\},$ $\{2,5,7\},$ $\{2,5,6,7,9\}$ es una de esas sucesiones, con $n=5.$ ¿Cuál es el residuo cuando $K$ se divide entre $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$

Solución:

Para una longitud fija $n,$ cada elemento de $\{1,\ldots,10\}$ o bien nunca aparece o bien aparece por primera vez en uno de $A_1,\ldots,A_n,$ dando $n+1$ opciones. Por lo tanto hay $(n+1)^{10}$ cadenas de longitud $n.$

Sumando, $K=\sum_{n=1}^{10}(n+1)^{10}=\sum_{k=2}^{11}k^{10}.$ Módulo $10,$ los términos $k=2,\ldots,11$ se reducen a $4,9,6,5,6,9,4,1,0,1,$ que suman $45\equiv 5.$

Por lo tanto, la respuesta correcta es 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 Problema 24

Solución:

El Problema 24 en otros años