2022 AMC 12A Problema 19

Question

Supón que

13

cartas numeradas

1,

2,

3,

\ldots,

13

están dispuestas en una fila. La tarea es recogerlas en orden numérico creciente, trabajando repetidamente de izquierda a derecha. En el ejemplo de abajo, las cartas

1,

2,

3

se recogen en la primera pasada,

4

y

5

en la segunda pasada,

6

en la tercera pasada,

7,

8,

9,

10

en la cuarta pasada, y

11,

12,

13

en la quinta pasada. ¿En cuántos de los

13!

posibles ordenamientos de las cartas se recogerán las

13

cartas en exactamente dos pasadas?

Suppose that

13

cards numbered

1,

2,

3,

\ldots,

13

are arranged in a row. The task is to pick them up in numerically increasing order, working repeatedly from left to right. In the example below, cards

1,

2,

3

are picked up on the first pass,

4

and

5

on the second pass,

6

on the third pass,

7,

8,

9,

10

on the fourth pass, and

11,

12,

13

on the fifth pass. For how many of the

13!

possible orderings of the cards will the

13

cards be picked up in exactly two passes?

4082

4095

4096

8178

8191

Respuesta: D

Conceptos:permutaciones reconocimiento de patrones

Nivel de dificultad: 2010

Pista pequeña:

Una nueva pasada comienza exactamente cuando el siguiente número a recoger está a la izquierda del anterior

A new pass begins exactly when the next number to pick up lies to the left of the previous one

Pista grande:

Dos pasadas significa que la sucesión de posiciones

\text{pos}(1),\ldots,\text{pos}(13)

tiene exactamente un descenso

Two passes means the sequence of positions

\text{pos}(1),\ldots,\text{pos}(13)

has exactly one descent

Solución:

Sea

\text{pos}(k)

la posición de la carta

k.

Se necesita una nueva pasada exactamente cuando

\text{pos}(k+1)\lt\text{pos}(k),

así que el número de pasadas es uno más que el número de descensos en la sucesión

\text{pos}(1),\text{pos}(2),\ldots,\text{pos}(13).

Para construir una permutación con a lo sumo un descenso, elige las entradas que van antes del posible descenso y escribe ambos bloques elegidos en orden creciente. Hay

2^{13}

subconjuntos. Los

14

segmentos iniciales

\varnothing,\{1\},\ldots,\{1,\ldots,13\}

no producen ningún descenso; cualquier otro subconjunto produce una única permutación con un descenso. Por lo tanto, el conteo es

2^{13}-14=8178.

Por lo tanto, la respuesta correcta es D.

Let

\text{pos}(k)

be the position of card

k.

A fresh pass is needed exactly when

\text{pos}(k+1)\lt\text{pos}(k),

so the number of passes is one more than the number of descents in the sequence

\text{pos}(1),\text{pos}(2),\ldots,\text{pos}(13).

To build a permutation with at most one descent, choose the entries before the possible descent and write both chosen blocks in increasing order. There are

2^{13}

subsets. The

14

initial segments

\varnothing,\{1\},\ldots,\{1,\ldots,13\}

produce no descent; every other subset produces a unique permutation with one descent. Hence the count is

2^{13}-14=8178.

Thus, the correct answer is D.