2022 AMC 10A Problem 22

Step 1: a small case. With $3$ cards, check all $6$ rows:

So $4$ rows take exactly two passes. Notice that in each of them the first pass takes $1, \ldots, k$ and the second pass takes the rest.

Step 2: what two passes means. A pass picks up cards in increasing order while moving to the right. So if the first pass collects $1, 2, \ldots, k$, those cards appear from left to right in increasing order. If the second pass collects all the rest, then $k + 1, \ldots, 13$ also appear from left to right in increasing order. Here $k$ is between $1$ and $12$.

Step 3: count rows made of two increasing groups. Fix $k$. To build such a row, choose which $k$ of the $13$ spots hold the small cards. Then the small cards fill those spots in increasing order, and the big cards fill the other spots in increasing order. So there are $\binom{13}{k}$ such rows.

Step 4: remove the one row that takes a single pass. One of those rows is $1, 2, \ldots, 13$ itself. Every other one takes exactly two passes. The first pass collects $1$ to $k$; could it keep going to $k + 1$? Only if $k + 1$ is to the right of $k$. But $k$ is the rightmost small card and $k + 1$ is the leftmost big card, so that would put every big card after every small card, which is the sorted row. So in every other row the first pass stops at $k$, and the second pass sweeps up $k + 1$ to $13$ in order. That gives $\binom{13}{k} - 1$ rows for this $k$.

Step 5: add over $k$. Different $k$ give different rows, since $k$ is how many cards the first pass collects. So the total is
$$\sum_{k=1}^{12} \left(\binom{13}{k} - 1\right).$$
All the $\binom{13}{k}$ from $k = 0$ to $13$ add to $2^{13} = 8192$ (the number of ways to pick any group of the $13$ spots). Leaving out $k = 0$ and $k = 13$ gives $8192 - 2 = 8190$. Then subtract the $12$ sorted rows: $8190 - 12 = 8178$.

Check with $3$ cards: $\left(\binom31 - 1\right) + \left(\binom32 - 1\right) = 2 + 2 = 4$, matching the table.

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

"Picked up in one pass" means "appears in increasing order", so a two-pass row is two increasing groups mixed together, and mixings are counted by choosing spots. The details to watch are the one sorted row for each $k$, which needs only one pass, and the fact that each row has only one possible $k$, so nothing is counted twice.

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