2022 AMC 10A Problem 22

Suppose the first pass collects exactly the cards $1, 2, \dots, k$ and the second pass collects $k+1, \dots, 13$, where $1 \le k \le 12$. A pass picks up cards in increasing order while scanning left to right, so in the row the cards $1, \dots, k$ appear in increasing order, and so do the cards $k+1, \dots, 13$.

Conversely, take any row in which both blocks $\{1,\dots,k\}$ and $\{k+1,\dots,13\}$ appear in increasing order. The first pass certainly collects $1, \dots, k$. It continues to $k+1$ only if $k+1$ sits to the right of $k$. But $k$ is the rightmost card of the first block and $k+1$ the leftmost of the second, so that would put the entire second block to the right of the entire first block, making the row $1, 2, \dots, 13$, which is collected in one pass. Every other such row takes exactly two passes, with the first pass ending at $k$.

For a fixed $k$, a row with both blocks increasing is determined by choosing which $k$ of the $13$ positions hold the first block: $\binom{13}{k}$ rows, of which one (the sorted row) must be excluded. Different $k$ give different rows, since $k$ is the number of cards collected in the first pass. Therefore the count is
$$\sum_{k=1}^{12} \left(\binom{13}{k} - 1\right) = \left(2^{13} - 2\right) - 12 = 8192 - 14 = 8178.$$

The answer is $\boxed{\textbf{(D)}\ 8178}$.

"Collected in one pass" is the same as "appears in increasing order," so a two-pass row is an interleaving of two increasing blocks, and interleavings are counted by choosing positions. The subtle points are the one degenerate interleaving per $k$ (the fully sorted row) and the fact that $k$ is determined by the row, so the cases do not overlap.

• Forgetting to exclude the sorted arrangement 1, 2, ..., 13 for each k (giving 8190), or letting k run to 13 or from 0 (giving 8191 or 8192).
• Believing rows can be double counted across different $k$; the split point is the size of the first pass, which the row itself fixes.