Question

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$

Solution:

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).$

Exactly two passes means exactly one descent. The number of permutations of $13$ elements with exactly one descent is the Eulerian number $\left\langle{13\atop1}\right\rangle=2^{13}-13-1=8178.$

Thus, the correct answer is D.

2022 AMC 12A Problem 19

Solution:

Problem 19 in Other Years