2023 AMC 12A Problema 24

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

Respuesta: C

Conceptos:subconjuntos principio de multiplicación aritmética modular

Nivel de dificultad: 2520

Pista pequeña:

Para un

n

fijo, cada uno de los

10

elementos elige independientemente el primer conjunto en el que entra, o nunca entra

For a fixed

n,

each of the

10

elements independently chooses the first set it enters, or never enters

Pista grande:

Eso da

(n+1)^{10}

cadenas, así que

K=\sum_{k=2}^{11}k^{10};

reduce cada término módulo

10

That gives

(n+1)^{10}

chains, so

K=\sum_{k=2}^{11}k^{10};

reduce each term modulo

10

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.