2022 AMC 10A Problem 22

Question

Suppose that

13

cards numbered

1,

2,

3,

\cdots,

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

Answer: D

Concepts:combinations complementary counting

Difficulty rating: 1660

Small hint:

The cards picked up on the first pass must occupy an increasing subsequence

Big hint:

Choose the positions of the first-pass cards and exclude one-pass arrangements

Solution:

Let

n

be the number of cards picked up on the first pass, where

1 \leq n \leq 12.

If we choose the spaces that the

n

cards occupy, the positions of the remaining cards are determined since they must be placed in order.

There are

\binom{13}{n}

ways to choose where the

n

cards go, but if the

n

cards are placed at the very beginning, then all the cards will be picked up on the first pass.

Therefore, for a given

n

there are

\binom{13}{n} - 1

ways to arrange the cards.

Summing over

1\le n\le12,

we get

\begin{gathered} \sum_{n=1}^{12}\left(\binom{13}{n}-1\right) \\ = (2^{13}-2)-12 \\ = 8178. \end{gathered}

Thus, D is the correct answer.