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.

2022 AMC 12A Problema 19

Respuesta: D

Nivel de dificultad: 2010

Pista pequeña:

Pista grande:

Solución:

El Problema 19 en otros años