2022 AMC 10A Problem 22

P21-25~7 minPrint

Basic Counting Arrangements with Restrictions Games & Processes Map the objects to something easier to count Split into exhaustive cases and handle each

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?

Show solution without answering

Key insight

Two passes means cards 1 to k appear in increasing order and so do cards k+1 to 13. Choosing which k spots hold the first group decides the whole row.

Solution

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

Row	Passes
$1\,2\,3$	$1$
$1\,3\,2$	$2$ (first $1, 2$ , then $3$ )
$2\,1\,3$	$2$ (first $1$ , then $2, 3$ )
$2\,3\,1$	$2$ (first $1$ , then $2, 3$ )
$3\,1\,2$	$2$ (first $1, 2$ , then $3$ )
$3\,2\,1$	$3$

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

Why this works

"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.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

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

Review in the AoPS books

Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.5)
Intermediate Counting & Probability, Chapter 13: Events With States (§13.4)
Intermediate Counting & Probability, Chapter 4: Constructive Counting and 1-1 Correspondences (§4.4, §4.5, §4.6)